oj.uz

답안 #26738

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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