oj.uz

Submission #769202

# Submission time Handle Problem Language Result Execution time Memory
769202 2023-06-29T09:50:37 Z Dan4Life Dancing Elephants (IOI11_elephants) C++17
50 / 100
 4391 ms 3196 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 = 380;
int n, L, a[mxN];

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){
        if(contains(x)) return;
        V.insert(lb(all(V),x),x); recalc();
    }
    void rem(int x){ 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] and bl[i].contains(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:40:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   40 |     if(SZ>B) return; vector<int> V3(SZ);
      |     ^~
elephants.cpp:40:22: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   40 |     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 1 ms 340 KB Output is correct
3 Correct 1 ms 424 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 1 ms 340 KB Output is correct
3 Correct 1 ms 424 KB Output is correct
4 Correct 1 ms 308 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 0 ms 312 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 1 ms 340 KB Output is correct
3 Correct 1 ms 424 KB Output is correct
4 Correct 1 ms 308 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 0 ms 312 KB Output is correct
7 Correct 1505 ms 1472 KB Output is correct
8 Correct 1763 ms 1896 KB Output is correct
9 Correct 3664 ms 3196 KB Output is correct
10 Correct 3238 ms 3120 KB Output is correct
11 Correct 2722 ms 3112 KB Output is correct
12 Correct 4391 ms 3120 KB Output is correct
13 Correct 3223 ms 2996 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 1 ms 340 KB Output is correct
3 Correct 1 ms 424 KB Output is correct
4 Correct 1 ms 308 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 0 ms 312 KB Output is correct
7 Correct 1505 ms 1472 KB Output is correct
8 Correct 1763 ms 1896 KB Output is correct
9 Correct 3664 ms 3196 KB Output is correct
10 Correct 3238 ms 3120 KB Output is correct
11 Correct 2722 ms 3112 KB Output is correct
12 Correct 4391 ms 3120 KB Output is correct
13 Correct 3223 ms 2996 KB Output is correct
14 Incorrect 422 ms 2216 KB Output isn't correct
15 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 1 ms 340 KB Output is correct
3 Correct 1 ms 424 KB Output is correct
4 Correct 1 ms 308 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 0 ms 312 KB Output is correct
7 Correct 1505 ms 1472 KB Output is correct
8 Correct 1763 ms 1896 KB Output is correct
9 Correct 3664 ms 3196 KB Output is correct
10 Correct 3238 ms 3120 KB Output is correct
11 Correct 2722 ms 3112 KB Output is correct
12 Correct 4391 ms 3120 KB Output is correct
13 Correct 3223 ms 2996 KB Output is correct
14 Incorrect 422 ms 2216 KB Output isn't correct
15 Halted 0 ms 0 KB -