oj.uz

Submission #769282

# Submission time Handle Problem Language Result Execution time Memory
769282 2023-06-29T11:26:12 Z Dan4Life Dancing Elephants (IOI11_elephants) C++17
97 / 100
 9000 ms 16200 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 = 400;
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 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 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 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 0 ms 340 KB Output is correct
7 Correct 475 ms 3788 KB Output is correct
8 Correct 906 ms 4088 KB Output is correct
9 Correct 3857 ms 5372 KB Output is correct
10 Correct 3317 ms 7180 KB Output is correct
11 Correct 3240 ms 7140 KB Output is correct
12 Correct 2745 ms 7044 KB Output is correct
13 Correct 3290 ms 7144 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 0 ms 340 KB Output is correct
7 Correct 475 ms 3788 KB Output is correct
8 Correct 906 ms 4088 KB Output is correct
9 Correct 3857 ms 5372 KB Output is correct
10 Correct 3317 ms 7180 KB Output is correct
11 Correct 3240 ms 7140 KB Output is correct
12 Correct 2745 ms 7044 KB Output is correct
13 Correct 3290 ms 7144 KB Output is correct
14 Correct 398 ms 3992 KB Output is correct
15 Correct 1194 ms 6444 KB Output is correct
16 Correct 3662 ms 7440 KB Output is correct
17 Correct 5544 ms 8876 KB Output is correct
18 Correct 5267 ms 8804 KB Output is correct
19 Correct 6671 ms 8784 KB Output is correct
20 Correct 5522 ms 8988 KB Output is correct
21 Correct 5603 ms 9008 KB Output is correct
22 Correct 6578 ms 9040 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 0 ms 340 KB Output is correct
7 Correct 475 ms 3788 KB Output is correct
8 Correct 906 ms 4088 KB Output is correct
9 Correct 3857 ms 5372 KB Output is correct
10 Correct 3317 ms 7180 KB Output is correct
11 Correct 3240 ms 7140 KB Output is correct
12 Correct 2745 ms 7044 KB Output is correct
13 Correct 3290 ms 7144 KB Output is correct
14 Correct 398 ms 3992 KB Output is correct
15 Correct 1194 ms 6444 KB Output is correct
16 Correct 3662 ms 7440 KB Output is correct
17 Correct 5544 ms 8876 KB Output is correct
18 Correct 5267 ms 8804 KB Output is correct
19 Correct 6671 ms 8784 KB Output is correct
20 Correct 5522 ms 8988 KB Output is correct
21 Correct 5603 ms 9008 KB Output is correct
22 Correct 6578 ms 9040 KB Output is correct
23 Execution timed out 9063 ms 16200 KB Time limit exceeded
24 Halted 0 ms 0 KB -