oj.uz

Submission #769296

# Submission time Handle Problem Language Result Execution time Memory
769296 2023-06-29T11:35:02 Z Dan4Life Dancing Elephants (IOI11_elephants) C++17
97 / 100
 9000 ms 16292 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 = 1000;
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; while(i and combine(i-1,i)) i--;
    i = xd; while(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 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 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 1 ms 340 KB Output is correct
4 Correct 1 ms 300 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 1 ms 340 KB Output is correct
4 Correct 1 ms 300 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 839 ms 3796 KB Output is correct
8 Correct 931 ms 4044 KB Output is correct
9 Correct 4073 ms 5332 KB Output is correct
10 Correct 3372 ms 7124 KB Output is correct
11 Correct 3191 ms 7148 KB Output is correct
12 Correct 2770 ms 7172 KB Output is correct
13 Correct 3278 ms 7104 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 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 300 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 839 ms 3796 KB Output is correct
8 Correct 931 ms 4044 KB Output is correct
9 Correct 4073 ms 5332 KB Output is correct
10 Correct 3372 ms 7124 KB Output is correct
11 Correct 3191 ms 7148 KB Output is correct
12 Correct 2770 ms 7172 KB Output is correct
13 Correct 3278 ms 7104 KB Output is correct
14 Correct 457 ms 4044 KB Output is correct
15 Correct 1130 ms 6496 KB Output is correct
16 Correct 3657 ms 7308 KB Output is correct
17 Correct 4877 ms 8744 KB Output is correct
18 Correct 4993 ms 8788 KB Output is correct
19 Correct 6546 ms 8844 KB Output is correct
20 Correct 5222 ms 8928 KB Output is correct
21 Correct 4926 ms 9068 KB Output is correct
22 Correct 6018 ms 9024 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 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 300 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 839 ms 3796 KB Output is correct
8 Correct 931 ms 4044 KB Output is correct
9 Correct 4073 ms 5332 KB Output is correct
10 Correct 3372 ms 7124 KB Output is correct
11 Correct 3191 ms 7148 KB Output is correct
12 Correct 2770 ms 7172 KB Output is correct
13 Correct 3278 ms 7104 KB Output is correct
14 Correct 457 ms 4044 KB Output is correct
15 Correct 1130 ms 6496 KB Output is correct
16 Correct 3657 ms 7308 KB Output is correct
17 Correct 4877 ms 8744 KB Output is correct
18 Correct 4993 ms 8788 KB Output is correct
19 Correct 6546 ms 8844 KB Output is correct
20 Correct 5222 ms 8928 KB Output is correct
21 Correct 4926 ms 9068 KB Output is correct
22 Correct 6018 ms 9024 KB Output is correct
23 Execution timed out 9071 ms 16292 KB Time limit exceeded
24 Halted 0 ms 0 KB -