oj.uz

Submission #769219

# Submission time Handle Problem Language Result Execution time Memory
769219 2023-06-29T10:04:02 Z Dan4Life Dancing Elephants (IOI11_elephants) C++17
50 / 100
 9000 ms 9032 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()
const int mxN = 150010;
const int B = 600;
int n, L, a[mxN];
map<int,int> cnt;
 
struct Block{
    vector<int> V;
    deque<array<int,2>> V2;
    Block(){V.clear();}
    void recalc(){
        V2.clear();
        for(int i = sz(V)-1; i>=0; i--){
            int pos = sz(V2)-(sz(V)-(int)(lb(all(V),V[i]+L+1)-begin(V)));
            if(pos==sz(V2)) V2.pf({1,V[i]+L+1});
            else V2.pf({V2[pos][0]+1,V2[pos][1]});
        }
    }
    Block(vector<int> XD){ V.swap(XD); recalc(); }
    bool contains(int x){
        int pos = lb(all(V),x)-begin(V);
        return (pos!=sz(V) and V[pos]==x);
    }
    void add(int x){
        cnt[x]++; if(cnt[x]!=1) return;
        V.insert(lb(all(V),x),x); recalc();
    }
    void rem(int x){ 
        cnt[x]--; if(cnt[x]!=0) 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.erase(begin(bl)+j); bl.erase(begin(bl)+i); bl.insert(begin(bl)+i,Block(V3));
} 
 
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.erase(begin(bl)+i); bl.insert(begin(bl)+i,B2); bl.insert(begin(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[sz(bl)-1].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:44:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   44 |     if(SZ>B) return; vector<int> V3(SZ);
      |     ^~
elephants.cpp:44:22: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   44 |     if(SZ>B) return; vector<int> V3(SZ);
      |                      ^~~~~~

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 300 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 300 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 300 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 2462 ms 3904 KB Output is correct
8 Correct 2713 ms 4240 KB Output is correct
9 Correct 4206 ms 5432 KB Output is correct
10 Correct 3970 ms 6816 KB Output is correct
11 Correct 3530 ms 6748 KB Output is correct
12 Correct 5299 ms 6776 KB Output is correct
13 Correct 4100 ms 6788 KB Output is correct

Subtask #4
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 300 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 2462 ms 3904 KB Output is correct
8 Correct 2713 ms 4240 KB Output is correct
9 Correct 4206 ms 5432 KB Output is correct
10 Correct 3970 ms 6816 KB Output is correct
11 Correct 3530 ms 6748 KB Output is correct
12 Correct 5299 ms 6776 KB Output is correct
13 Correct 4100 ms 6788 KB Output is correct
14 Correct 1716 ms 4012 KB Output is correct
15 Correct 2899 ms 5844 KB Output is correct
16 Correct 7377 ms 7456 KB Output is correct
17 Execution timed out 9034 ms 9032 KB Time limit exceeded
18 Halted 0 ms 0 KB -

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 300 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 2462 ms 3904 KB Output is correct
8 Correct 2713 ms 4240 KB Output is correct
9 Correct 4206 ms 5432 KB Output is correct
10 Correct 3970 ms 6816 KB Output is correct
11 Correct 3530 ms 6748 KB Output is correct
12 Correct 5299 ms 6776 KB Output is correct
13 Correct 4100 ms 6788 KB Output is correct
14 Correct 1716 ms 4012 KB Output is correct
15 Correct 2899 ms 5844 KB Output is correct
16 Correct 7377 ms 7456 KB Output is correct
17 Execution timed out 9034 ms 9032 KB Time limit exceeded
18 Halted 0 ms 0 KB -