oj.uz

답안 #122716

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
122716 2019-06-29T07:25:56 Z nvmdava 코끼리 (Dancing Elephants) (IOI11_elephants) C++17
97 / 100
 9000 ms 12876 KB 
#include "elephants.h"
#include <bits/stdc++.h>
#define ff first
#define ss second
#define pii pair<int, int>
using namespace std;
#define SQ 400
int n, l;
int loc[150005];
int bid[150005];

vector<vector<pair<int , pii> > > buck;
vector<pair<int, pii> > emp;
//{LOC {count, last} }


int find(){
   int res = 0;
   int lst = -1;
   for(auto& v : buck){
      if(v.empty() || v.back().ff <= lst) continue;
      int id = upper_bound(v.begin(), v.end(), lst, [](const int& lhs, const pair<int, pii>& rhs){
         return lhs < rhs.ff;
      }) - v.begin();
      res += v[id].ss.ff;
      lst = v[id].ss.ss;
   }
   return res;
}

void recalc(vector<pair<int, pii> >& vec){
   int sz = vec.size();
   int r = sz;
   for(int l = sz - 1; l >= 0; l--){
      while(vec[r - 1].ff > vec[l].ff + ::l) r--;
      vec[l].ss.ff = (r == sz ? 0 : vec[r].ss.ff) + 1;
      vec[l].ss.ss = (r == sz ? vec[l].ff + ::l : vec[r].ss.ss);
   }
}
vector<pii> sorted;
void renew(){
   for(int i = 0; i < n; i++){
      sorted[i].ff = loc[i];
      sorted[i].ss = i;
   }
   sort(sorted.begin(), sorted.end());
   buck.clear();
   for(int i = 0; i < n; i++){
      if(i % SQ == 0){
         buck.push_back(emp);
      }
      buck.back().push_back({sorted[i].ff, {0, 0}});
      bid[sorted[i].ss] = i / SQ;
   }
   for(auto& x : buck){
      recalc(x);
   }
}
void init(int N, int L, int X[]){
   n = N; l = L;
   for(int i = 0; i < n; i++){
      loc[i] = X[i];
   }
   sorted.resize(n);
   renew();
}
int cnt = 0;
void erase(vector<pair<int, pii> >& buck, int x){
   for(int i = 1; i < buck.size(); i++){
      if(buck[i - 1].ff == x) swap(buck[i - 1], buck[i]);
   }
   buck.pop_back();
   recalc(buck);
}
void insert(vector<pair<int, pii> >& buck, int x){
   buck.push_back({x, {0, 0}});
   int i = buck.size() - 1;
   while(i != 0 && buck[i - 1].ff > buck[i].ff){
      swap(buck[i - 1], buck[i]);
      i--;
   }
   recalc(buck);
}
int update(int j, int y){
   if(loc[j] == y) return find();
   if(++cnt % SQ == 0){
      loc[j] = y;
      renew();
   } else {
      erase(buck[bid[j]], loc[j]);
      for(int i = 0; i < buck.size(); i++){
         if(buck[i].back().ff >= y){
            insert(buck[i], y);
            loc[j] = y;
            bid[j] = i;
            break;
         }
      }
      if(loc[j] != y){
         insert(buck.back(), y);
         loc[j] = y;
         bid[j] = buck.size() - 1;
      }
   }
   return find();
}

Compilation message

elephants.cpp: In function 'void erase(std::vector<std::pair<int, std::pair<int, int> > >&, int)':
elephants.cpp:69:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int i = 1; i < buck.size(); i++){
                   ~~^~~~~~~~~~~~~
elephants.cpp: In function 'int update(int, int)':
elephants.cpp:91:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for(int i = 0; i < buck.size(); i++){
                      ~~^~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 380 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 504 KB Output is correct

Subtask #2
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 380 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 504 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 380 KB Output is correct
6 Correct 2 ms 404 KB Output is correct

Subtask #3
24.0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 380 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 504 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 380 KB Output is correct
6 Correct 2 ms 404 KB Output is correct
7 Correct 337 ms 2588 KB Output is correct
8 Correct 375 ms 2900 KB Output is correct
9 Correct 588 ms 4456 KB Output is correct
10 Correct 724 ms 4296 KB Output is correct
11 Correct 714 ms 4416 KB Output is correct
12 Correct 1153 ms 4380 KB Output is correct
13 Correct 809 ms 4156 KB Output is correct

Subtask #4
47.0 / 47.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 380 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 504 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 380 KB Output is correct
6 Correct 2 ms 404 KB Output is correct
7 Correct 337 ms 2588 KB Output is correct
8 Correct 375 ms 2900 KB Output is correct
9 Correct 588 ms 4456 KB Output is correct
10 Correct 724 ms 4296 KB Output is correct
11 Correct 714 ms 4416 KB Output is correct
12 Correct 1153 ms 4380 KB Output is correct
13 Correct 809 ms 4156 KB Output is correct
14 Correct 529 ms 3528 KB Output is correct
15 Correct 581 ms 3584 KB Output is correct
16 Correct 1816 ms 4948 KB Output is correct
17 Correct 2093 ms 6096 KB Output is correct
18 Correct 2190 ms 5992 KB Output is correct
19 Correct 1356 ms 6000 KB Output is correct
20 Correct 2104 ms 5972 KB Output is correct
21 Correct 2039 ms 6056 KB Output is correct
22 Correct 1439 ms 5548 KB Output is correct

Subtask #5
0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 380 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 504 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 380 KB Output is correct
6 Correct 2 ms 404 KB Output is correct
7 Correct 337 ms 2588 KB Output is correct
8 Correct 375 ms 2900 KB Output is correct
9 Correct 588 ms 4456 KB Output is correct
10 Correct 724 ms 4296 KB Output is correct
11 Correct 714 ms 4416 KB Output is correct
12 Correct 1153 ms 4380 KB Output is correct
13 Correct 809 ms 4156 KB Output is correct
14 Correct 529 ms 3528 KB Output is correct
15 Correct 581 ms 3584 KB Output is correct
16 Correct 1816 ms 4948 KB Output is correct
17 Correct 2093 ms 6096 KB Output is correct
18 Correct 2190 ms 5992 KB Output is correct
19 Correct 1356 ms 6000 KB Output is correct
20 Correct 2104 ms 5972 KB Output is correct
21 Correct 2039 ms 6056 KB Output is correct
22 Correct 1439 ms 5548 KB Output is correct
23 Correct 4811 ms 12812 KB Output is correct
24 Correct 5174 ms 12836 KB Output is correct
25 Correct 4077 ms 12804 KB Output is correct
26 Correct 5852 ms 12876 KB Output is correct
27 Correct 6311 ms 12684 KB Output is correct
28 Correct 1602 ms 5372 KB Output is correct
29 Correct 1542 ms 5240 KB Output is correct
30 Correct 1594 ms 5340 KB Output is correct
31 Correct 1535 ms 5316 KB Output is correct
32 Correct 5664 ms 12276 KB Output is correct
33 Correct 5289 ms 11640 KB Output is correct
34 Correct 5856 ms 12448 KB Output is correct
35 Correct 5607 ms 12720 KB Output is correct
36 Correct 170 ms 11896 KB Output is correct
37 Execution timed out 9081 ms 12708 KB Time limit exceeded
38 Halted 0 ms 0 KB -