oj.uz

Submission #769235

# Submission time Handle Problem Language Result Execution time Memory
769235 2023-06-29T10:21:32 Z Dan4Life Dancing Elephants (IOI11_elephants) C++17
97 / 100
 9000 ms 15976 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 = 500;
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(); }
    bool contains(int x){
        int pos = lb(all(V),x)-begin(V);
        return (pos!=sz(V) and V[pos]==x);
    }
    void add(int x){
        cnt[x]++; if(cnt[x]!=1) return;
        V.insert(lb(all(V),x),x); recalc();
    }
    void rem(int x){ 
        cnt[x]--; if(cnt[x]!=0) 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.erase(begin(bl)+j); bl.erase(begin(bl)+i); bl.insert(begin(bl)+i,Block(V3));
} 
 
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.erase(begin(bl)+i); bl.insert(begin(bl)+i,B2); bl.insert(begin(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[sz(bl)-1].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:43:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   43 |     if(SZ>B) return; vector<int> V3(SZ);
      |     ^~
elephants.cpp:43:22: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   43 |     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 0 ms 340 KB Output is correct
2 Correct 0 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 0 ms 340 KB Output is correct
2 Correct 0 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 1 ms 340 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 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 1 ms 340 KB Output is correct
7 Correct 887 ms 3724 KB Output is correct
8 Correct 1075 ms 4080 KB Output is correct
9 Correct 3477 ms 5412 KB Output is correct
10 Correct 3981 ms 7004 KB Output is correct
11 Correct 3869 ms 7008 KB Output is correct
12 Correct 3343 ms 7108 KB Output is correct
13 Correct 4131 ms 6948 KB Output is correct

Subtask #4
47.0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 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 1 ms 340 KB Output is correct
7 Correct 887 ms 3724 KB Output is correct
8 Correct 1075 ms 4080 KB Output is correct
9 Correct 3477 ms 5412 KB Output is correct
10 Correct 3981 ms 7004 KB Output is correct
11 Correct 3869 ms 7008 KB Output is correct
12 Correct 3343 ms 7108 KB Output is correct
13 Correct 4131 ms 6948 KB Output is correct
14 Correct 573 ms 4048 KB Output is correct
15 Correct 2338 ms 6504 KB Output is correct
16 Correct 4235 ms 7428 KB Output is correct
17 Correct 6190 ms 8824 KB Output is correct
18 Correct 6251 ms 8800 KB Output is correct
19 Correct 7320 ms 8812 KB Output is correct
20 Correct 6545 ms 8960 KB Output is correct
21 Correct 6416 ms 9004 KB Output is correct
22 Correct 7481 ms 8756 KB Output is correct

Subtask #5
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 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 1 ms 340 KB Output is correct
7 Correct 887 ms 3724 KB Output is correct
8 Correct 1075 ms 4080 KB Output is correct
9 Correct 3477 ms 5412 KB Output is correct
10 Correct 3981 ms 7004 KB Output is correct
11 Correct 3869 ms 7008 KB Output is correct
12 Correct 3343 ms 7108 KB Output is correct
13 Correct 4131 ms 6948 KB Output is correct
14 Correct 573 ms 4048 KB Output is correct
15 Correct 2338 ms 6504 KB Output is correct
16 Correct 4235 ms 7428 KB Output is correct
17 Correct 6190 ms 8824 KB Output is correct
18 Correct 6251 ms 8800 KB Output is correct
19 Correct 7320 ms 8812 KB Output is correct
20 Correct 6545 ms 8960 KB Output is correct
21 Correct 6416 ms 9004 KB Output is correct
22 Correct 7481 ms 8756 KB Output is correct
23 Execution timed out 9094 ms 15976 KB Time limit exceeded
24 Halted 0 ms 0 KB -