oj.uz

Submission #769251

# Submission time Handle Problem Language Result Execution time Memory
769251 2023-06-29T10:50:48 Z Dan4Life Dancing Elephants (IOI11_elephants) C++17
97 / 100
 9000 ms 16164 KB 
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#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+3];
    Block(){}
    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(); }
    void add(int x){
        if(++cnt[x]!=1) return;
        V.insert(lb(all(V),x),x); recalc();
    }
    void rem(int x){ 
        if(--cnt[x]) return;
        V.erase(lb(all(V),x)); recalc(); 
    }
};
vector<Block> bl;
 
bool 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 0; vector<int> V3(SZ);
    merge(all(bl[i].V),all(bl[j].V),begin(V3));
    bl[i]=Block(V3), bl.erase(begin(bl)+j); return 1;
} 
 
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.insert(begin(bl)+i+1,B2); bl[i]=B1;
}
 
void init(int N, int l, int A[]){
    bl.push_back({}); L = l; n = N;
    for(int i = 0; i < n; i++)
        a[i] = A[i], bl.back().add(a[i]), divide(sz(bl)-1);
}

int findBl(int x){
    int l = 0, r = sz(bl)-1;
    while(l<r){
        int mid = (l+r)/2;
        if(bl[mid].V.back()<x) l=mid+1;
        else r=mid;
    }
    return l;
}

int update(int p, int y){
    int i = findBl(a[p]);
    bl[i].rem(a[p]); 
    int xd = i;
    while(i and combine(i-1,i)) i--;
    i = xd; while(i<sz(bl)-1 and combine(i,i+1)) i++;
    a[p] = y; i = findBl(a[p]);
    bl[i].add(a[p]); divide(i);
    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 'bool combine(int, int)':
elephants.cpp:38:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   38 |     if(SZ>B) return 0; vector<int> V3(SZ);
      |     ^~
elephants.cpp:38:24: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   38 |     if(SZ>B) return 0; vector<int> V3(SZ);
      |                        ^~~~~~
elephants.cpp: In function 'void init(int, int, int*)':
elephants.cpp:13:8: warning: '<anonymous>.Block::V2' may be used uninitialized in this function [-Wmaybe-uninitialized]
   13 | 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 280 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 280 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 880 ms 3796 KB Output is correct
8 Correct 1072 ms 4116 KB Output is correct
9 Correct 4387 ms 5320 KB Output is correct
10 Correct 2917 ms 7060 KB Output is correct
11 Correct 2840 ms 7164 KB Output is correct
12 Correct 2986 ms 7104 KB Output is correct
13 Correct 2938 ms 7196 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 280 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 880 ms 3796 KB Output is correct
8 Correct 1072 ms 4116 KB Output is correct
9 Correct 4387 ms 5320 KB Output is correct
10 Correct 2917 ms 7060 KB Output is correct
11 Correct 2840 ms 7164 KB Output is correct
12 Correct 2986 ms 7104 KB Output is correct
13 Correct 2938 ms 7196 KB Output is correct
14 Correct 567 ms 4012 KB Output is correct
15 Correct 1348 ms 6440 KB Output is correct
16 Correct 4086 ms 7420 KB Output is correct
17 Correct 5536 ms 8704 KB Output is correct
18 Correct 5384 ms 8764 KB Output is correct
19 Correct 6728 ms 8744 KB Output is correct
20 Correct 5870 ms 9028 KB Output is correct
21 Correct 6046 ms 9056 KB Output is correct
22 Correct 5749 ms 9124 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 280 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 880 ms 3796 KB Output is correct
8 Correct 1072 ms 4116 KB Output is correct
9 Correct 4387 ms 5320 KB Output is correct
10 Correct 2917 ms 7060 KB Output is correct
11 Correct 2840 ms 7164 KB Output is correct
12 Correct 2986 ms 7104 KB Output is correct
13 Correct 2938 ms 7196 KB Output is correct
14 Correct 567 ms 4012 KB Output is correct
15 Correct 1348 ms 6440 KB Output is correct
16 Correct 4086 ms 7420 KB Output is correct
17 Correct 5536 ms 8704 KB Output is correct
18 Correct 5384 ms 8764 KB Output is correct
19 Correct 6728 ms 8744 KB Output is correct
20 Correct 5870 ms 9028 KB Output is correct
21 Correct 6046 ms 9056 KB Output is correct
22 Correct 5749 ms 9124 KB Output is correct
23 Execution timed out 9061 ms 16164 KB Time limit exceeded
24 Halted 0 ms 0 KB -