oj.uz

Submission #769244

# Submission time Handle Problem Language Result Execution time Memory
769244 2023-06-29T10:33:11 Z Dan4Life Dancing Elephants (IOI11_elephants) C++17
97 / 100
 9000 ms 16244 KB 
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define pf push_front
#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 = 550;
int n, L, a[mxN];
unordered_map<int,int> cnt;
 
struct Block{
    vector<int> V; ar V2[B+10];
    Block(){V.clear();}
    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;
 
void 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; vector<int> V3(SZ);
    merge(all(bl[i].V),all(bl[j].V),begin(V3));
    bl[i]=Block(V3), bl.erase(begin(bl)+j);
} 
 
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.pb({}); 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 update(int p, int y){
    for(int i = 0; i < sz(bl); i++){
        if(bl[i].V.back()>=a[p]){ 
            bl[i].rem(a[p]); 
            if(i) combine(i-1,i);
            if(i<sz(bl)-1) combine(i,i+1);
            break;
        }
    }
    a[p] = y;
    for(int i = 0; i < sz(bl); i++){
        if(i==sz(bl)-1 or bl[i].V.back() >= a[p]){
            bl[i].add(a[p]); divide(i); break;
        }
    }
    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 'void combine(int, int)':
elephants.cpp:39:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   39 |     if(SZ>B) return; vector<int> V3(SZ);
      |     ^~
elephants.cpp:39:22: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   39 |     if(SZ>B) return; vector<int> V3(SZ);
      |                      ^~~~~~
elephants.cpp: In function 'void init(int, int, int*)':
elephants.cpp:14:8: warning: '<anonymous>.Block::V2' may be used uninitialized in this function [-Wmaybe-uninitialized]
   14 | 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 1 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 1 ms 340 KB Output is correct
7 Correct 972 ms 3692 KB Output is correct
8 Correct 1385 ms 4128 KB Output is correct
9 Correct 3544 ms 5272 KB Output is correct
10 Correct 4081 ms 7184 KB Output is correct
11 Correct 4072 ms 7116 KB Output is correct
12 Correct 3510 ms 7064 KB Output is correct
13 Correct 4365 ms 7092 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 1 ms 340 KB Output is correct
7 Correct 972 ms 3692 KB Output is correct
8 Correct 1385 ms 4128 KB Output is correct
9 Correct 3544 ms 5272 KB Output is correct
10 Correct 4081 ms 7184 KB Output is correct
11 Correct 4072 ms 7116 KB Output is correct
12 Correct 3510 ms 7064 KB Output is correct
13 Correct 4365 ms 7092 KB Output is correct
14 Correct 680 ms 3968 KB Output is correct
15 Correct 2380 ms 6472 KB Output is correct
16 Correct 4455 ms 7480 KB Output is correct
17 Correct 6092 ms 8816 KB Output is correct
18 Correct 6235 ms 8800 KB Output is correct
19 Correct 7776 ms 8820 KB Output is correct
20 Correct 6411 ms 9024 KB Output is correct
21 Correct 6358 ms 8984 KB Output is correct
22 Correct 7872 ms 9004 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 1 ms 340 KB Output is correct
7 Correct 972 ms 3692 KB Output is correct
8 Correct 1385 ms 4128 KB Output is correct
9 Correct 3544 ms 5272 KB Output is correct
10 Correct 4081 ms 7184 KB Output is correct
11 Correct 4072 ms 7116 KB Output is correct
12 Correct 3510 ms 7064 KB Output is correct
13 Correct 4365 ms 7092 KB Output is correct
14 Correct 680 ms 3968 KB Output is correct
15 Correct 2380 ms 6472 KB Output is correct
16 Correct 4455 ms 7480 KB Output is correct
17 Correct 6092 ms 8816 KB Output is correct
18 Correct 6235 ms 8800 KB Output is correct
19 Correct 7776 ms 8820 KB Output is correct
20 Correct 6411 ms 9024 KB Output is correct
21 Correct 6358 ms 8984 KB Output is correct
22 Correct 7872 ms 9004 KB Output is correct
23 Execution timed out 9096 ms 16244 KB Time limit exceeded
24 Halted 0 ms 0 KB -