oj.uz

Submission #769254

# Submission time Handle Problem Language Result Execution time Memory
769254 2023-06-29T10:54:48 Z Dan4Life Dancing Elephants (IOI11_elephants) C++17
97 / 100
 9000 ms 16164 KB 
#pragma GCC optimize("Ofast")
#pragma GCC target("avx2")
#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:40:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   40 |     if(SZ>B) return 0; vector<int> V3(SZ);
      |     ^~
elephants.cpp:40:24: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   40 |     if(SZ>B) return 0; vector<int> V3(SZ);
      |                        ^~~~~~
elephants.cpp: In function 'void init(int, int, int*)':
elephants.cpp:15:8: warning: '<anonymous>.Block::V2' may be used uninitialized in this function [-Wmaybe-uninitialized]
   15 | struct Block{
      |        ^~~~~

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 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 1 ms 340 KB Output is correct
2 Correct 1 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 1 ms 340 KB Output is correct
2 Correct 1 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 938 ms 3804 KB Output is correct
8 Correct 1150 ms 4092 KB Output is correct
9 Correct 4512 ms 5444 KB Output is correct
10 Correct 2961 ms 7080 KB Output is correct
11 Correct 2852 ms 7104 KB Output is correct
12 Correct 3082 ms 7052 KB Output is correct
13 Correct 2956 ms 7116 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 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 938 ms 3804 KB Output is correct
8 Correct 1150 ms 4092 KB Output is correct
9 Correct 4512 ms 5444 KB Output is correct
10 Correct 2961 ms 7080 KB Output is correct
11 Correct 2852 ms 7104 KB Output is correct
12 Correct 3082 ms 7052 KB Output is correct
13 Correct 2956 ms 7116 KB Output is correct
14 Correct 572 ms 3944 KB Output is correct
15 Correct 1450 ms 6416 KB Output is correct
16 Correct 4101 ms 7344 KB Output is correct
17 Correct 5691 ms 8812 KB Output is correct
18 Correct 5441 ms 8748 KB Output is correct
19 Correct 7233 ms 8880 KB Output is correct
20 Correct 5954 ms 9024 KB Output is correct
21 Correct 5980 ms 9044 KB Output is correct
22 Correct 5669 ms 9056 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 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 938 ms 3804 KB Output is correct
8 Correct 1150 ms 4092 KB Output is correct
9 Correct 4512 ms 5444 KB Output is correct
10 Correct 2961 ms 7080 KB Output is correct
11 Correct 2852 ms 7104 KB Output is correct
12 Correct 3082 ms 7052 KB Output is correct
13 Correct 2956 ms 7116 KB Output is correct
14 Correct 572 ms 3944 KB Output is correct
15 Correct 1450 ms 6416 KB Output is correct
16 Correct 4101 ms 7344 KB Output is correct
17 Correct 5691 ms 8812 KB Output is correct
18 Correct 5441 ms 8748 KB Output is correct
19 Correct 7233 ms 8880 KB Output is correct
20 Correct 5954 ms 9024 KB Output is correct
21 Correct 5980 ms 9044 KB Output is correct
22 Correct 5669 ms 9056 KB Output is correct
23 Execution timed out 9060 ms 16164 KB Time limit exceeded
24 Halted 0 ms 0 KB -