oj.uz

Submission #769281

# Submission time Handle Problem Language Result Execution time Memory
769281 2023-06-29T11:24:52 Z Dan4Life Dancing Elephants (IOI11_elephants) C++17
97 / 100
 9000 ms 16180 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(){ int j = sz(V);
        for(int i = sz(V)-1; i>=0; i--){
            while(V[j-1]>=V[i]+L+1) j--;
            if(j==sz(V)) V2[i]=ar({1,V[i]+L+1});
            else V2[i]=ar({V2[j][0]+1,V2[j][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));
    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 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 1 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 1 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 547 ms 4072 KB Output is correct
8 Correct 895 ms 4192 KB Output is correct
9 Correct 3932 ms 5436 KB Output is correct
10 Correct 3315 ms 7368 KB Output is correct
11 Correct 3277 ms 7260 KB Output is correct
12 Correct 2769 ms 7276 KB Output is correct
13 Correct 3220 ms 7284 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 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 547 ms 4072 KB Output is correct
8 Correct 895 ms 4192 KB Output is correct
9 Correct 3932 ms 5436 KB Output is correct
10 Correct 3315 ms 7368 KB Output is correct
11 Correct 3277 ms 7260 KB Output is correct
12 Correct 2769 ms 7276 KB Output is correct
13 Correct 3220 ms 7284 KB Output is correct
14 Correct 421 ms 4116 KB Output is correct
15 Correct 1112 ms 6492 KB Output is correct
16 Correct 3488 ms 7580 KB Output is correct
17 Correct 5182 ms 8772 KB Output is correct
18 Correct 5001 ms 8752 KB Output is correct
19 Correct 6407 ms 8760 KB Output is correct
20 Correct 5467 ms 9144 KB Output is correct
21 Correct 5525 ms 9068 KB Output is correct
22 Correct 6423 ms 9256 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 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 547 ms 4072 KB Output is correct
8 Correct 895 ms 4192 KB Output is correct
9 Correct 3932 ms 5436 KB Output is correct
10 Correct 3315 ms 7368 KB Output is correct
11 Correct 3277 ms 7260 KB Output is correct
12 Correct 2769 ms 7276 KB Output is correct
13 Correct 3220 ms 7284 KB Output is correct
14 Correct 421 ms 4116 KB Output is correct
15 Correct 1112 ms 6492 KB Output is correct
16 Correct 3488 ms 7580 KB Output is correct
17 Correct 5182 ms 8772 KB Output is correct
18 Correct 5001 ms 8752 KB Output is correct
19 Correct 6407 ms 8760 KB Output is correct
20 Correct 5467 ms 9144 KB Output is correct
21 Correct 5525 ms 9068 KB Output is correct
22 Correct 6423 ms 9256 KB Output is correct
23 Execution timed out 9061 ms 16180 KB Time limit exceeded
24 Halted 0 ms 0 KB -