oj.uz

Submission #769293

# Submission time Handle Problem Language Result Execution time Memory
769293 2023-06-29T11:32:57 Z Dan4Life Dancing Elephants (IOI11_elephants) C++17
97 / 100
 9000 ms 16248 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; if(i and combine(i-1,i)) i--;
    i = xd; if(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 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 611 ms 3740 KB Output is correct
8 Correct 850 ms 4152 KB Output is correct
9 Correct 3944 ms 5436 KB Output is correct
10 Correct 3327 ms 7376 KB Output is correct
11 Correct 3322 ms 7236 KB Output is correct
12 Correct 2642 ms 7140 KB Output is correct
13 Correct 3323 ms 7136 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 611 ms 3740 KB Output is correct
8 Correct 850 ms 4152 KB Output is correct
9 Correct 3944 ms 5436 KB Output is correct
10 Correct 3327 ms 7376 KB Output is correct
11 Correct 3322 ms 7236 KB Output is correct
12 Correct 2642 ms 7140 KB Output is correct
13 Correct 3323 ms 7136 KB Output is correct
14 Correct 459 ms 4012 KB Output is correct
15 Correct 1089 ms 6420 KB Output is correct
16 Correct 3455 ms 7328 KB Output is correct
17 Correct 4777 ms 8680 KB Output is correct
18 Correct 5230 ms 8728 KB Output is correct
19 Correct 6238 ms 8836 KB Output is correct
20 Correct 4970 ms 9120 KB Output is correct
21 Correct 5104 ms 9164 KB Output is correct
22 Correct 6309 ms 9116 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 611 ms 3740 KB Output is correct
8 Correct 850 ms 4152 KB Output is correct
9 Correct 3944 ms 5436 KB Output is correct
10 Correct 3327 ms 7376 KB Output is correct
11 Correct 3322 ms 7236 KB Output is correct
12 Correct 2642 ms 7140 KB Output is correct
13 Correct 3323 ms 7136 KB Output is correct
14 Correct 459 ms 4012 KB Output is correct
15 Correct 1089 ms 6420 KB Output is correct
16 Correct 3455 ms 7328 KB Output is correct
17 Correct 4777 ms 8680 KB Output is correct
18 Correct 5230 ms 8728 KB Output is correct
19 Correct 6238 ms 8836 KB Output is correct
20 Correct 4970 ms 9120 KB Output is correct
21 Correct 5104 ms 9164 KB Output is correct
22 Correct 6309 ms 9116 KB Output is correct
23 Execution timed out 9068 ms 16248 KB Time limit exceeded
24 Halted 0 ms 0 KB -