Submission #26738

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
26738	2017-07-05T10:56:39 Z	model_code	Meteors (POI11_met)	C++11	100 / 100	3416 ms	42952 KB

/*************************************************************************
 *                                                                       *
 *                    XVIII Olimpiada Informatyczna                      *
 *                                                                       *
 *   Zadanie:           Meteory                                          *
 *   Autor:             Blazej Osinski                                   *
 *   Zlozonosc czasowa: O((m+k)*lg(m)*lg(k))                             *
 *   Opis:              Rozwiazanie alternatywne                         *
 *                                                                       *
 *************************************************************************/

#include<cstdio>
#include<vector>
#include<algorithm>
#include<cassert>
using namespace std;

int __abc;
#define scanf __abc=scanf

const int N = 300007;

static const int INF = 1000000000;

//*****  Drzewo potęgowe  ***** {{{

struct DrzewoPotegowe {
    static const int WD = 524377;
    long long s[WD];
    int wd;
    DrzewoPotegowe(int n);
    void czysc();
    void dodaj_wartosc(int a, int wart);
    long long suma(int w);
};

DrzewoPotegowe::DrzewoPotegowe(int n){
  wd = 1;
  while ((1<<wd) < n)
    wd++;
  czysc();
}

void DrzewoPotegowe::czysc(){
  for(int i = 1; i <= (1<<wd); i++)
    s[i] = 0;
}

long long DrzewoPotegowe::suma(int w)
{
  w++;
  if (w == 0)
    return 0LL;
  long long suma = 0LL;
  int p = 1;
  while (w > 0) {
    if (p & w){
      suma += s[w];
      w ^= p;
    }
    p <<= 1;
  }
  return suma;
}

void DrzewoPotegowe::dodaj_wartosc(int a, int wart){
  a++;
  for (int i = 0, p = 1; i <= wd; i++, p <<= 1){
    if (a & p){
      s[a] += wart;
      a += p;
    }
  }
}

//******************************************** }}}

int n, m, pot[N], wl[N], z, srodki[N];
pair<int, int> przed[N];
vector<pair<int, int> > grupy[N];
long long suma[N];

int main()
{
  // Wczytywanie danych. 
  scanf("%d %d", &n, &m);
  for(int i = 0; i < m; i++){
    scanf("%d", &z);
    z--;
    wl[i] = z;
  }
  for(int i = 0; i < n; i++)
    scanf("%d", &pot[i]);
  
  // Wczytywanie zapytań.
  scanf("%d", &z);
  for(int i = 0; i < z; i++){
    int l, r, a;
    scanf("%d %d %d", &l, &r, &a);
    l--;
    r--;
    if (l <= r){
      grupy[l].push_back(make_pair(i, a));
      grupy[r+1].push_back(make_pair(i, -a));
    }
    else {
      grupy[0].push_back(make_pair(i, a));
      grupy[r+1].push_back(make_pair(i, -a));
      grupy[l].push_back(make_pair(i, a));
      grupy[m].push_back(make_pair(i, -a));
    }
  }

  // Wspólne wyszukiwanie binarne
  DrzewoPotegowe dpot(z);
  for(int i = 0; i < n; i++)
    przed[i] = make_pair(0, z);
  
  for(;;){
    int l = 0;
    for (int i = 0; i < n; i++){
      suma[i] = 0LL;
      if (przed[i].first != przed[i].second){
        srodki[i] = (przed[i].first + przed[i].second)/2;
        l++;
      }
      else
        srodki[i] = -1;
    } 
    if (l == 0)
      break;

    // Zamiast symulacji przegladamy wydarzenia dla kolejnych stacji.
    dpot.czysc(); 
    for (int i = 0; i < m; i++){
      for (vector<pair<int, int> >::iterator it = grupy[i].begin(); it != grupy[i].end(); ++it){
        dpot.dodaj_wartosc(it->first, it->second);
      }
      if (srodki[wl[i]] != -1)
      {
        // Właściciel tej stacji nie jest jeszcze rozpatrzony.
        suma[wl[i]] += dpot.suma(srodki[wl[i]]);
        if(suma[wl[i]] > INF)
          suma[wl[i]] = INF;
      }
    }
    for (int i = 0; i < n; i++){
      if (przed[i].first != przed[i].second){
        if ((long long)pot[i] <= suma[i]) // i-te państwo dostało co najmniej tyle co potrzebowało. 
          przed[i].second = srodki[i];
        else
          przed[i].first = srodki[i]+1;
      }
    }
  }
  for(int i = 0; i < n; i++){
    if(przed[i].first < z)
      printf("%d\n", przed[i].first+1);
    else
      printf("NIE\n");
  }
  return 0;
}

Subtask #1
12.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	20384 KB	Output is correct
2	Correct	3 ms	20380 KB	Output is correct
3	Correct	3 ms	20384 KB	Output is correct

Subtask #2
12.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	20384 KB	Output is correct
2	Correct	3 ms	20380 KB	Output is correct
3	Correct	6 ms	20380 KB	Output is correct

Subtask #3
12.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	269 ms	22100 KB	Output is correct
2	Correct	353 ms	23304 KB	Output is correct
3	Correct	336 ms	22280 KB	Output is correct

Subtask #4
12.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	349 ms	22652 KB	Output is correct
2	Correct	349 ms	22648 KB	Output is correct
3	Correct	363 ms	23308 KB	Output is correct
4	Correct	43 ms	20644 KB	Output is correct

Subtask #5
13.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	169 ms	22520 KB	Output is correct
2	Correct	243 ms	23544 KB	Output is correct
3	Correct	193 ms	21996 KB	Output is correct
4	Correct	313 ms	22264 KB	Output is correct

Subtask #6
13.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	316 ms	23300 KB	Output is correct
2	Correct	343 ms	23316 KB	Output is correct
3	Correct	269 ms	22232 KB	Output is correct
4	Correct	283 ms	22668 KB	Output is correct

Subtask #7
13.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3263 ms	34948 KB	Output is correct
2	Correct	1646 ms	42952 KB	Output is correct
3	Correct	1126 ms	26860 KB	Output is correct
4	Correct	3416 ms	35084 KB	Output is correct

Subtask #8
13.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3286 ms	34948 KB	Output is correct
2	Correct	1213 ms	34756 KB	Output is correct
3	Correct	953 ms	27000 KB	Output is correct
4	Correct	3359 ms	35436 KB	Output is correct

Submission #26738

Compilation message