oj.uz

Submission #769295

# Submission time Handle Problem Language Result Execution time Memory
769295 2023-06-29T11:34:39 Z Dan4Life Dancing Elephants (IOI11_elephants) C++17
97 / 100
 9000 ms 16228 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 = 800;
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: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 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 0 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 0 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 525 ms 3800 KB Output is correct
8 Correct 850 ms 4048 KB Output is correct
9 Correct 3899 ms 5364 KB Output is correct
10 Correct 3271 ms 7172 KB Output is correct
11 Correct 3288 ms 7088 KB Output is correct
12 Correct 2670 ms 7192 KB Output is correct
13 Correct 3263 ms 7160 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 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 525 ms 3800 KB Output is correct
8 Correct 850 ms 4048 KB Output is correct
9 Correct 3899 ms 5364 KB Output is correct
10 Correct 3271 ms 7172 KB Output is correct
11 Correct 3288 ms 7088 KB Output is correct
12 Correct 2670 ms 7192 KB Output is correct
13 Correct 3263 ms 7160 KB Output is correct
14 Correct 506 ms 3968 KB Output is correct
15 Correct 1285 ms 6472 KB Output is correct
16 Correct 3677 ms 7360 KB Output is correct
17 Correct 4764 ms 8756 KB Output is correct
18 Correct 4993 ms 8688 KB Output is correct
19 Correct 6367 ms 8868 KB Output is correct
20 Correct 5075 ms 8956 KB Output is correct
21 Correct 5240 ms 9024 KB Output is correct
22 Correct 6504 ms 9076 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 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 525 ms 3800 KB Output is correct
8 Correct 850 ms 4048 KB Output is correct
9 Correct 3899 ms 5364 KB Output is correct
10 Correct 3271 ms 7172 KB Output is correct
11 Correct 3288 ms 7088 KB Output is correct
12 Correct 2670 ms 7192 KB Output is correct
13 Correct 3263 ms 7160 KB Output is correct
14 Correct 506 ms 3968 KB Output is correct
15 Correct 1285 ms 6472 KB Output is correct
16 Correct 3677 ms 7360 KB Output is correct
17 Correct 4764 ms 8756 KB Output is correct
18 Correct 4993 ms 8688 KB Output is correct
19 Correct 6367 ms 8868 KB Output is correct
20 Correct 5075 ms 8956 KB Output is correct
21 Correct 5240 ms 9024 KB Output is correct
22 Correct 6504 ms 9076 KB Output is correct
23 Execution timed out 9026 ms 16228 KB Time limit exceeded
24 Halted 0 ms 0 KB -