oj.uz

Submission #769216

# Submission time Handle Problem Language Result Execution time Memory
769216 2023-06-29T10:01:33 Z Dan4Life Dancing Elephants (IOI11_elephants) C++17
97 / 100
 9000 ms 15312 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()
const int mxN = 150010;
const int B = 500;
int n, L, a[mxN];
unordered_map<int,int> cnt;
 
struct Block{
    vector<int> V;
    deque<array<int,2>> V2;
    Block(){V.clear();}
    void recalc(){
        V2.clear();
        for(int i = sz(V)-1; i>=0; i--){
            int pos = sz(V2)-(sz(V)-(int)(lb(all(V),V[i]+L+1)-begin(V)));
            if(pos==sz(V2)) V2.pf({1,V[i]+L+1});
            else V2.pf({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:44:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   44 |     if(SZ>B) return; vector<int> V3(SZ);
      |     ^~
elephants.cpp:44:22: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   44 |     if(SZ>B) return; vector<int> V3(SZ);
      |                      ^~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 1 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 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 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 0 ms 340 KB Output is correct
7 Correct 1939 ms 3708 KB Output is correct
8 Correct 2201 ms 3948 KB Output is correct
9 Correct 3692 ms 5228 KB Output is correct
10 Correct 3413 ms 6604 KB Output is correct
11 Correct 3012 ms 6760 KB Output is correct
12 Correct 4840 ms 6876 KB Output is correct
13 Correct 3389 ms 6620 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 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 0 ms 340 KB Output is correct
7 Correct 1939 ms 3708 KB Output is correct
8 Correct 2201 ms 3948 KB Output is correct
9 Correct 3692 ms 5228 KB Output is correct
10 Correct 3413 ms 6604 KB Output is correct
11 Correct 3012 ms 6760 KB Output is correct
12 Correct 4840 ms 6876 KB Output is correct
13 Correct 3389 ms 6620 KB Output is correct
14 Correct 1412 ms 3908 KB Output is correct
15 Correct 2474 ms 6440 KB Output is correct
16 Correct 6469 ms 7324 KB Output is correct
17 Correct 8289 ms 8564 KB Output is correct
18 Correct 8219 ms 8496 KB Output is correct
19 Correct 6064 ms 8416 KB Output is correct
20 Correct 8851 ms 8652 KB Output is correct
21 Correct 8473 ms 8648 KB Output is correct
22 Correct 5990 ms 8380 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 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 0 ms 340 KB Output is correct
7 Correct 1939 ms 3708 KB Output is correct
8 Correct 2201 ms 3948 KB Output is correct
9 Correct 3692 ms 5228 KB Output is correct
10 Correct 3413 ms 6604 KB Output is correct
11 Correct 3012 ms 6760 KB Output is correct
12 Correct 4840 ms 6876 KB Output is correct
13 Correct 3389 ms 6620 KB Output is correct
14 Correct 1412 ms 3908 KB Output is correct
15 Correct 2474 ms 6440 KB Output is correct
16 Correct 6469 ms 7324 KB Output is correct
17 Correct 8289 ms 8564 KB Output is correct
18 Correct 8219 ms 8496 KB Output is correct
19 Correct 6064 ms 8416 KB Output is correct
20 Correct 8851 ms 8652 KB Output is correct
21 Correct 8473 ms 8648 KB Output is correct
22 Correct 5990 ms 8380 KB Output is correct
23 Execution timed out 9056 ms 15312 KB Time limit exceeded
24 Halted 0 ms 0 KB -