oj.uz

Submission #769232

# Submission time Handle Problem Language Result Execution time Memory
769232 2023-06-29T10:19:49 Z Dan4Life Dancing Elephants (IOI11_elephants) C++17
97 / 100
 9000 ms 15948 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 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 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 782 ms 3908 KB Output is correct
8 Correct 1329 ms 4172 KB Output is correct
9 Correct 3546 ms 5440 KB Output is correct
10 Correct 4032 ms 7208 KB Output is correct
11 Correct 3997 ms 7072 KB Output is correct
12 Correct 3386 ms 7240 KB Output is correct
13 Correct 4302 ms 7064 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 0 ms 340 KB Output is correct
7 Correct 782 ms 3908 KB Output is correct
8 Correct 1329 ms 4172 KB Output is correct
9 Correct 3546 ms 5440 KB Output is correct
10 Correct 4032 ms 7208 KB Output is correct
11 Correct 3997 ms 7072 KB Output is correct
12 Correct 3386 ms 7240 KB Output is correct
13 Correct 4302 ms 7064 KB Output is correct
14 Correct 789 ms 4160 KB Output is correct
15 Correct 2434 ms 6508 KB Output is correct
16 Correct 4587 ms 7392 KB Output is correct
17 Correct 6566 ms 8840 KB Output is correct
18 Correct 6370 ms 8720 KB Output is correct
19 Correct 7407 ms 8740 KB Output is correct
20 Correct 6358 ms 9112 KB Output is correct
21 Correct 6303 ms 9016 KB Output is correct
22 Correct 7250 ms 8900 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 0 ms 340 KB Output is correct
7 Correct 782 ms 3908 KB Output is correct
8 Correct 1329 ms 4172 KB Output is correct
9 Correct 3546 ms 5440 KB Output is correct
10 Correct 4032 ms 7208 KB Output is correct
11 Correct 3997 ms 7072 KB Output is correct
12 Correct 3386 ms 7240 KB Output is correct
13 Correct 4302 ms 7064 KB Output is correct
14 Correct 789 ms 4160 KB Output is correct
15 Correct 2434 ms 6508 KB Output is correct
16 Correct 4587 ms 7392 KB Output is correct
17 Correct 6566 ms 8840 KB Output is correct
18 Correct 6370 ms 8720 KB Output is correct
19 Correct 7407 ms 8740 KB Output is correct
20 Correct 6358 ms 9112 KB Output is correct
21 Correct 6303 ms 9016 KB Output is correct
22 Correct 7250 ms 8900 KB Output is correct
23 Execution timed out 9038 ms 15948 KB Time limit exceeded
24 Halted 0 ms 0 KB -