oj.uz

Submission #769256

# Submission time Handle Problem Language Result Execution time Memory
769256 2023-06-29T10:58:04 Z Dan4Life Dancing Elephants (IOI11_elephants) C++17
97 / 100
 9000 ms 16200 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 'int update(int, int)':
elephants.cpp:71:50: warning: statement has no effect [-Wunused-value]
   71 |     i = xd; while(i<sz(bl)-1 and combine(i,i+1)) i;
      |                                                  ^
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 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 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 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 776 ms 3688 KB Output is correct
8 Correct 1222 ms 4196 KB Output is correct
9 Correct 4700 ms 5292 KB Output is correct
10 Correct 3751 ms 7140 KB Output is correct
11 Correct 3554 ms 7252 KB Output is correct
12 Correct 3194 ms 7056 KB Output is correct
13 Correct 3803 ms 7340 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 0 ms 340 KB Output is correct
7 Correct 776 ms 3688 KB Output is correct
8 Correct 1222 ms 4196 KB Output is correct
9 Correct 4700 ms 5292 KB Output is correct
10 Correct 3751 ms 7140 KB Output is correct
11 Correct 3554 ms 7252 KB Output is correct
12 Correct 3194 ms 7056 KB Output is correct
13 Correct 3803 ms 7340 KB Output is correct
14 Correct 548 ms 3984 KB Output is correct
15 Correct 1404 ms 6536 KB Output is correct
16 Correct 4051 ms 7516 KB Output is correct
17 Correct 5855 ms 8784 KB Output is correct
18 Correct 5803 ms 8732 KB Output is correct
19 Correct 7165 ms 8792 KB Output is correct
20 Correct 6162 ms 9016 KB Output is correct
21 Correct 6059 ms 9080 KB Output is correct
22 Correct 6957 ms 9128 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 0 ms 340 KB Output is correct
7 Correct 776 ms 3688 KB Output is correct
8 Correct 1222 ms 4196 KB Output is correct
9 Correct 4700 ms 5292 KB Output is correct
10 Correct 3751 ms 7140 KB Output is correct
11 Correct 3554 ms 7252 KB Output is correct
12 Correct 3194 ms 7056 KB Output is correct
13 Correct 3803 ms 7340 KB Output is correct
14 Correct 548 ms 3984 KB Output is correct
15 Correct 1404 ms 6536 KB Output is correct
16 Correct 4051 ms 7516 KB Output is correct
17 Correct 5855 ms 8784 KB Output is correct
18 Correct 5803 ms 8732 KB Output is correct
19 Correct 7165 ms 8792 KB Output is correct
20 Correct 6162 ms 9016 KB Output is correct
21 Correct 6059 ms 9080 KB Output is correct
22 Correct 6957 ms 9128 KB Output is correct
23 Execution timed out 9089 ms 16200 KB Time limit exceeded
24 Halted 0 ms 0 KB -