Codeforces Round #179 (Div1 A, Div2 C) – Greg and Array

Problem description: C. Greg and Array

This problem is simple when you are fast with sweep line solutions. First you need to kwon that for each query the range [x, y] will be increased by one. This means that if a range [l, r] will be called 6 times the d value will be used 6 times on each value in the range.

When calling 6 times: the range [l=2, r=3] with d=4 will be:

a[2] += 4; a[3] += 4;
a[2] += 4; a[3] += 4;
a[2] += 4; a[3] += 4;
a[2] += 4; a[3] += 4;
a[2] += 4; a[3] += 4;
a[2] += 4; a[3] += 4;

A better way to do this is multiplying the value d by the number of times, d * times-that-it-is-called like this:

a[2] += 4*6; a[3] += 4*6; // d*c <-- remember this

Using that logic now we can create our new values of d.

  for(int i=0; i<k ;i++) {
    scanf("%d %d", &x, &y);
    inc[ x-1 ]++; // when the range [x, y] begins add one extra 'd'
    inc[ y ]--; // when the range [x, y] ends remove the extra 'd' added.
  }

  LL c = 0;
  for(int i=0; i<m ;i++) {
    c += inc[i];
    LL newValueD = LL(d[i])*c; // d*c <-- do you remember this?
  }

Using the same logic we can create the new a values.

The next code obtained Accepted.

#include <stdio.h>
using namespace std;
typedef long long   LL;

int n, m, k;
int l[100000], r[100000], d[100000], inc[100001], a[100000];
LL dInA[100001];

int main(){
  int x, y;
  scanf("%d %d %d", &n, &m, &k);
  for(int i=0; i<n ;i++) {
    scanf("%d", &x);
    a[i] = x;
  }
  for(int i=0; i<m ;i++) {
    scanf("%d %d %d", &l[i], &r[i], &d[i]);
  }
  for(int i=0; i<k ;i++) {
    scanf("%d %d", &x, &y);
    inc[ x-1 ]++;
    inc[ y ]--;
  }

  LL c = 0;
  for(int i=0; i<m ;i++) {
    c += inc[i];
    LL newValueD = c * LL(d[i]);
    dInA[ l[i]-1 ] += newValueD;
    dInA[ r[i] ] -= newValueD;
  }
  c = 0;
  for(int i=0; i<n ;i++) {
    c += dInA[i];
    if(i) printf(" ");
    printf("%I64d", c+LL(a[i]));
  }
  printf("n");
}

This is an O(n + m + k) solution of the problem.

Screen-Shot-2013-04-15-at-10.44.47-PM

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión /  Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión /  Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión /  Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión /  Cambiar )

Conectando a %s