oj.uz

Submission #769217

# Submission time Handle Problem Language Result Execution time Memory
769217 2023-06-29T10:03:22 Z Dan4Life Dancing Elephants (IOI11_elephants) C++17
97 / 100
 9000 ms 14940 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];
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 0 ms 340 KB Output is correct
2 Correct 0 ms 340 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 0 ms 340 KB Output is correct
2 Correct 0 ms 340 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 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 0 ms 340 KB Output is correct
2 Correct 0 ms 340 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 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 1517 ms 3960 KB Output is correct
8 Correct 1829 ms 4296 KB Output is correct
9 Correct 3526 ms 5480 KB Output is correct
10 Correct 3222 ms 6696 KB Output is correct
11 Correct 2988 ms 6672 KB Output is correct
12 Correct 4548 ms 6880 KB Output is correct
13 Correct 3266 ms 6676 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 1 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 1517 ms 3960 KB Output is correct
8 Correct 1829 ms 4296 KB Output is correct
9 Correct 3526 ms 5480 KB Output is correct
10 Correct 3222 ms 6696 KB Output is correct
11 Correct 2988 ms 6672 KB Output is correct
12 Correct 4548 ms 6880 KB Output is correct
13 Correct 3266 ms 6676 KB Output is correct
14 Correct 1194 ms 4080 KB Output is correct
15 Correct 2386 ms 6016 KB Output is correct
16 Correct 5879 ms 7492 KB Output is correct
17 Correct 7896 ms 9204 KB Output is correct
18 Correct 8153 ms 9152 KB Output is correct
19 Correct 5892 ms 9212 KB Output is correct
20 Correct 8186 ms 9468 KB Output is correct
21 Correct 8018 ms 9524 KB Output is correct
22 Correct 6089 ms 9232 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 1 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 1517 ms 3960 KB Output is correct
8 Correct 1829 ms 4296 KB Output is correct
9 Correct 3526 ms 5480 KB Output is correct
10 Correct 3222 ms 6696 KB Output is correct
11 Correct 2988 ms 6672 KB Output is correct
12 Correct 4548 ms 6880 KB Output is correct
13 Correct 3266 ms 6676 KB Output is correct
14 Correct 1194 ms 4080 KB Output is correct
15 Correct 2386 ms 6016 KB Output is correct
16 Correct 5879 ms 7492 KB Output is correct
17 Correct 7896 ms 9204 KB Output is correct
18 Correct 8153 ms 9152 KB Output is correct
19 Correct 5892 ms 9212 KB Output is correct
20 Correct 8186 ms 9468 KB Output is correct
21 Correct 8018 ms 9524 KB Output is correct
22 Correct 6089 ms 9232 KB Output is correct
23 Execution timed out 9023 ms 14940 KB Time limit exceeded
24 Halted 0 ms 0 KB -