oj.uz

Submission #769237

# Submission time Handle Problem Language Result Execution time Memory
769237 2023-06-29T10:21:48 Z Dan4Life Dancing Elephants (IOI11_elephants) C++17
97 / 100
 9000 ms 15920 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 = 400;
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 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 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 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 1 ms 340 KB Output is correct
7 Correct 781 ms 3780 KB Output is correct
8 Correct 1264 ms 4140 KB Output is correct
9 Correct 3281 ms 5300 KB Output is correct
10 Correct 3740 ms 6944 KB Output is correct
11 Correct 3618 ms 7016 KB Output is correct
12 Correct 3213 ms 7068 KB Output is correct
13 Correct 3908 ms 6908 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 1 ms 340 KB Output is correct
7 Correct 781 ms 3780 KB Output is correct
8 Correct 1264 ms 4140 KB Output is correct
9 Correct 3281 ms 5300 KB Output is correct
10 Correct 3740 ms 6944 KB Output is correct
11 Correct 3618 ms 7016 KB Output is correct
12 Correct 3213 ms 7068 KB Output is correct
13 Correct 3908 ms 6908 KB Output is correct
14 Correct 587 ms 3972 KB Output is correct
15 Correct 2117 ms 6512 KB Output is correct
16 Correct 4119 ms 7388 KB Output is correct
17 Correct 5679 ms 8864 KB Output is correct
18 Correct 5636 ms 8796 KB Output is correct
19 Correct 7358 ms 8868 KB Output is correct
20 Correct 6054 ms 9060 KB Output is correct
21 Correct 5998 ms 9044 KB Output is correct
22 Correct 7366 ms 8784 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 1 ms 340 KB Output is correct
7 Correct 781 ms 3780 KB Output is correct
8 Correct 1264 ms 4140 KB Output is correct
9 Correct 3281 ms 5300 KB Output is correct
10 Correct 3740 ms 6944 KB Output is correct
11 Correct 3618 ms 7016 KB Output is correct
12 Correct 3213 ms 7068 KB Output is correct
13 Correct 3908 ms 6908 KB Output is correct
14 Correct 587 ms 3972 KB Output is correct
15 Correct 2117 ms 6512 KB Output is correct
16 Correct 4119 ms 7388 KB Output is correct
17 Correct 5679 ms 8864 KB Output is correct
18 Correct 5636 ms 8796 KB Output is correct
19 Correct 7358 ms 8868 KB Output is correct
20 Correct 6054 ms 9060 KB Output is correct
21 Correct 5998 ms 9044 KB Output is correct
22 Correct 7366 ms 8784 KB Output is correct
23 Execution timed out 9050 ms 15920 KB Time limit exceeded
24 Halted 0 ms 0 KB -