oj.uz

Submission #769255

# Submission time Handle Problem Language Result Execution time Memory
769255 2023-06-29T10:57:47 Z Dan4Life Dancing Elephants (IOI11_elephants) C++17
97 / 100
 9000 ms 16260 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 'int update(int, int)':
elephants.cpp:73:50: warning: statement has no effect [-Wunused-value]
   73 |     i = xd; while(i<sz(bl)-1 and combine(i,i+1)) i;
      |                                                  ^
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 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 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 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 1 ms 340 KB Output is correct
7 Correct 830 ms 3712 KB Output is correct
8 Correct 1199 ms 4056 KB Output is correct
9 Correct 4279 ms 5332 KB Output is correct
10 Correct 3576 ms 7208 KB Output is correct
11 Correct 3466 ms 7172 KB Output is correct
12 Correct 3169 ms 7104 KB Output is correct
13 Correct 3759 ms 7148 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 1 ms 340 KB Output is correct
7 Correct 830 ms 3712 KB Output is correct
8 Correct 1199 ms 4056 KB Output is correct
9 Correct 4279 ms 5332 KB Output is correct
10 Correct 3576 ms 7208 KB Output is correct
11 Correct 3466 ms 7172 KB Output is correct
12 Correct 3169 ms 7104 KB Output is correct
13 Correct 3759 ms 7148 KB Output is correct
14 Correct 588 ms 3984 KB Output is correct
15 Correct 1507 ms 6504 KB Output is correct
16 Correct 4290 ms 7436 KB Output is correct
17 Correct 5761 ms 8808 KB Output is correct
18 Correct 5770 ms 8812 KB Output is correct
19 Correct 6986 ms 8768 KB Output is correct
20 Correct 5815 ms 9048 KB Output is correct
21 Correct 6071 ms 9076 KB Output is correct
22 Correct 6999 ms 9044 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 1 ms 340 KB Output is correct
7 Correct 830 ms 3712 KB Output is correct
8 Correct 1199 ms 4056 KB Output is correct
9 Correct 4279 ms 5332 KB Output is correct
10 Correct 3576 ms 7208 KB Output is correct
11 Correct 3466 ms 7172 KB Output is correct
12 Correct 3169 ms 7104 KB Output is correct
13 Correct 3759 ms 7148 KB Output is correct
14 Correct 588 ms 3984 KB Output is correct
15 Correct 1507 ms 6504 KB Output is correct
16 Correct 4290 ms 7436 KB Output is correct
17 Correct 5761 ms 8808 KB Output is correct
18 Correct 5770 ms 8812 KB Output is correct
19 Correct 6986 ms 8768 KB Output is correct
20 Correct 5815 ms 9048 KB Output is correct
21 Correct 6071 ms 9076 KB Output is correct
22 Correct 6999 ms 9044 KB Output is correct
23 Execution timed out 9040 ms 16260 KB Time limit exceeded
24 Halted 0 ms 0 KB -