oj.uz

Submission #769212

# Submission time Handle Problem Language Result Execution time Memory
769212 2023-06-29T09:59:19 Z Dan4Life Dancing Elephants (IOI11_elephants) C++17
97 / 100
 9000 ms 20432 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 = 380;
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 1 ms 308 KB Output is correct
3 Correct 1 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 308 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 308 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 1 ms 340 KB Output is correct
2 Correct 1 ms 308 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 308 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1515 ms 4096 KB Output is correct
8 Correct 1845 ms 4556 KB Output is correct
9 Correct 3448 ms 5560 KB Output is correct
10 Correct 3280 ms 7248 KB Output is correct
11 Correct 2857 ms 7240 KB Output is correct
12 Correct 4465 ms 7392 KB Output is correct
13 Correct 3364 ms 7204 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 308 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 308 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1515 ms 4096 KB Output is correct
8 Correct 1845 ms 4556 KB Output is correct
9 Correct 3448 ms 5560 KB Output is correct
10 Correct 3280 ms 7248 KB Output is correct
11 Correct 2857 ms 7240 KB Output is correct
12 Correct 4465 ms 7392 KB Output is correct
13 Correct 3364 ms 7204 KB Output is correct
14 Correct 1236 ms 4412 KB Output is correct
15 Correct 2497 ms 7972 KB Output is correct
16 Correct 6151 ms 8992 KB Output is correct
17 Correct 7784 ms 10512 KB Output is correct
18 Correct 7701 ms 10500 KB Output is correct
19 Correct 5811 ms 10808 KB Output is correct
20 Correct 8037 ms 10720 KB Output is correct
21 Correct 7963 ms 10788 KB Output is correct
22 Correct 6056 ms 10004 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 308 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 308 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1515 ms 4096 KB Output is correct
8 Correct 1845 ms 4556 KB Output is correct
9 Correct 3448 ms 5560 KB Output is correct
10 Correct 3280 ms 7248 KB Output is correct
11 Correct 2857 ms 7240 KB Output is correct
12 Correct 4465 ms 7392 KB Output is correct
13 Correct 3364 ms 7204 KB Output is correct
14 Correct 1236 ms 4412 KB Output is correct
15 Correct 2497 ms 7972 KB Output is correct
16 Correct 6151 ms 8992 KB Output is correct
17 Correct 7784 ms 10512 KB Output is correct
18 Correct 7701 ms 10500 KB Output is correct
19 Correct 5811 ms 10808 KB Output is correct
20 Correct 8037 ms 10720 KB Output is correct
21 Correct 7963 ms 10788 KB Output is correct
22 Correct 6056 ms 10004 KB Output is correct
23 Execution timed out 9086 ms 20432 KB Time limit exceeded
24 Halted 0 ms 0 KB -