oj.uz

Submission #769242

# Submission time Handle Problem Language Result Execution time Memory
769242 2023-06-29T10:31:04 Z Dan4Life Dancing Elephants (IOI11_elephants) C++17
97 / 100
 9000 ms 16300 KB 
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define pf push_front
#define lb lower_bound
#define sz(a) (int)a.size()
#define all(a) a.begin(),a.end()
using ar = array<int,2>;
const int mxN = 150010;
const int B = 380;
int n, L, a[mxN];
unordered_map<int,int> cnt;
 
struct Block{
    vector<int> V; ar V2[B+10];
    Block(){V.clear();}
    void recalc(){
        for(int i = sz(V)-1; i>=0; i--){
            int pos = lb(begin(V)+i,end(V),V[i]+L+1)-begin(V);
            if(pos==sz(V)) V2[i]=ar({1,V[i]+L+1});
            else V2[i]=ar({V2[pos][0]+1,V2[pos][1]});
        }
    }
    Block(vector<int> XD){ V.swap(XD); recalc(); }
    void add(int x){
        if(++cnt[x]!=1) return;
        V.insert(lb(all(V),x),x); recalc();
    }
    void rem(int x){ 
        if(--cnt[x]) return;
        V.erase(lb(all(V),x)); recalc(); 
    }
};
vector<Block> bl;
 
void combine(int i, int j){
    if(i>j) swap(i,j); 
    int SZ = sz(bl[i].V)+sz(bl[j].V);
    if(SZ>B) return; vector<int> V3(SZ);
    merge(all(bl[i].V),all(bl[j].V),begin(V3));
    bl[i]=Block(V3), bl.erase(begin(bl)+j);
} 
 
void divide(int i){
    int mid = sz(bl[i].V)/2; if(mid*2<=B) return;
    auto B1 = Block(vector<int>(begin(bl[i].V),begin(bl[i].V)+mid));
    auto B2 = Block(vector<int>(begin(bl[i].V)+mid,end(bl[i].V)));
    bl.insert(begin(bl)+i+1,B2); bl[i]=B1;
}
 
void init(int N, int l, int A[]){
    bl.pb({}); L = l; n = N;
    for(int i = 0; i < n; i++)
        a[i] = A[i], bl.back().add(a[i]), divide(sz(bl)-1);
}
 
int update(int p, int y){
    for(int i = 0; i < sz(bl); i++){
        if(bl[i].V.back()>=a[p]){ 
            bl[i].rem(a[p]); 
            if(i) combine(i-1,i);
            if(i<sz(bl)-1) combine(i,i+1);
            break;
        }
    }
    a[p] = y;
    for(int i = 0; i < sz(bl); i++){
        if(i==sz(bl)-1 or bl[i].V.back() >= a[p]){
            bl[i].add(a[p]); divide(i); break;
        }
    }
    int ans = 0, pos = 0;
    for(Block cur : bl){
        if(!sz(cur.V) or cur.V.back()<pos) continue;
        auto p = lb(all(cur.V),pos)-begin(cur.V);
        ans+=cur.V2[p][0], pos = cur.V2[p][1];
    }
    return ans;
}

Compilation message

elephants.cpp: In function 'void combine(int, int)':
elephants.cpp:39:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   39 |     if(SZ>B) return; vector<int> V3(SZ);
      |     ^~
elephants.cpp:39:22: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   39 |     if(SZ>B) return; vector<int> V3(SZ);
      |                      ^~~~~~
elephants.cpp: In function 'void init(int, int, int*)':
elephants.cpp:14:8: warning: '<anonymous>.Block::V2' may be used uninitialized in this function [-Wmaybe-uninitialized]
   14 | struct Block{
      |        ^~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 767 ms 3792 KB Output is correct
8 Correct 1210 ms 4128 KB Output is correct
9 Correct 3250 ms 5368 KB Output is correct
10 Correct 3680 ms 7292 KB Output is correct
11 Correct 3605 ms 7164 KB Output is correct
12 Correct 3126 ms 7088 KB Output is correct
13 Correct 3780 ms 7196 KB Output is correct

Subtask #4
47.0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 767 ms 3792 KB Output is correct
8 Correct 1210 ms 4128 KB Output is correct
9 Correct 3250 ms 5368 KB Output is correct
10 Correct 3680 ms 7292 KB Output is correct
11 Correct 3605 ms 7164 KB Output is correct
12 Correct 3126 ms 7088 KB Output is correct
13 Correct 3780 ms 7196 KB Output is correct
14 Correct 595 ms 3924 KB Output is correct
15 Correct 2163 ms 6604 KB Output is correct
16 Correct 4061 ms 7488 KB Output is correct
17 Correct 5660 ms 8888 KB Output is correct
18 Correct 5643 ms 8824 KB Output is correct
19 Correct 7195 ms 8872 KB Output is correct
20 Correct 6044 ms 9084 KB Output is correct
21 Correct 5880 ms 9060 KB Output is correct
22 Correct 7196 ms 9144 KB Output is correct

Subtask #5
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 767 ms 3792 KB Output is correct
8 Correct 1210 ms 4128 KB Output is correct
9 Correct 3250 ms 5368 KB Output is correct
10 Correct 3680 ms 7292 KB Output is correct
11 Correct 3605 ms 7164 KB Output is correct
12 Correct 3126 ms 7088 KB Output is correct
13 Correct 3780 ms 7196 KB Output is correct
14 Correct 595 ms 3924 KB Output is correct
15 Correct 2163 ms 6604 KB Output is correct
16 Correct 4061 ms 7488 KB Output is correct
17 Correct 5660 ms 8888 KB Output is correct
18 Correct 5643 ms 8824 KB Output is correct
19 Correct 7195 ms 8872 KB Output is correct
20 Correct 6044 ms 9084 KB Output is correct
21 Correct 5880 ms 9060 KB Output is correct
22 Correct 7196 ms 9144 KB Output is correct
23 Execution timed out 9063 ms 16300 KB Time limit exceeded
24 Halted 0 ms 0 KB -