oj.uz

Submission #769200

# Submission time Handle Problem Language Result Execution time Memory
769200 2023-06-29T09:49:48 Z Dan4Life Dancing Elephants (IOI11_elephants) C++17
50 / 100
 3906 ms 3916 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 = 50010;
const int B = 250;
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){
        //for(auto u : cur.V) cout << u << " "; cout << "\n";
        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 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 1 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 1 ms 340 KB Output is correct
2 Correct 1 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 1302 ms 1324 KB Output is correct
8 Correct 1491 ms 2512 KB Output is correct
9 Correct 3432 ms 3916 KB Output is correct
10 Correct 3342 ms 3632 KB Output is correct
11 Correct 2923 ms 3480 KB Output is correct
12 Correct 3906 ms 3808 KB Output is correct
13 Correct 3453 ms 3332 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 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 1302 ms 1324 KB Output is correct
8 Correct 1491 ms 2512 KB Output is correct
9 Correct 3432 ms 3916 KB Output is correct
10 Correct 3342 ms 3632 KB Output is correct
11 Correct 2923 ms 3480 KB Output is correct
12 Correct 3906 ms 3808 KB Output is correct
13 Correct 3453 ms 3332 KB Output is correct
14 Incorrect 321 ms 3276 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 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 1302 ms 1324 KB Output is correct
8 Correct 1491 ms 2512 KB Output is correct
9 Correct 3432 ms 3916 KB Output is correct
10 Correct 3342 ms 3632 KB Output is correct
11 Correct 2923 ms 3480 KB Output is correct
12 Correct 3906 ms 3808 KB Output is correct
13 Correct 3453 ms 3332 KB Output is correct
14 Incorrect 321 ms 3276 KB Output isn't correct
15 Halted 0 ms 0 KB -