oj.uz

Submission #769283

# Submission time Handle Problem Language Result Execution time Memory
769283 2023-06-29T11:26:33 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; if(i and combine(i-1,i)) i--;
    i = xd; if(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 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 447 ms 3768 KB Output is correct
8 Correct 919 ms 4116 KB Output is correct
9 Correct 4074 ms 5304 KB Output is correct
10 Correct 3396 ms 7248 KB Output is correct
11 Correct 3401 ms 7136 KB Output is correct
12 Correct 2931 ms 7068 KB Output is correct
13 Correct 3362 ms 7120 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 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 447 ms 3768 KB Output is correct
8 Correct 919 ms 4116 KB Output is correct
9 Correct 4074 ms 5304 KB Output is correct
10 Correct 3396 ms 7248 KB Output is correct
11 Correct 3401 ms 7136 KB Output is correct
12 Correct 2931 ms 7068 KB Output is correct
13 Correct 3362 ms 7120 KB Output is correct
14 Correct 401 ms 3984 KB Output is correct
15 Correct 1259 ms 6536 KB Output is correct
16 Correct 3574 ms 7412 KB Output is correct
17 Correct 5294 ms 8828 KB Output is correct
18 Correct 5062 ms 8744 KB Output is correct
19 Correct 6882 ms 8744 KB Output is correct
20 Correct 5524 ms 9044 KB Output is correct
21 Correct 5500 ms 9004 KB Output is correct
22 Correct 6403 ms 9124 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 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 447 ms 3768 KB Output is correct
8 Correct 919 ms 4116 KB Output is correct
9 Correct 4074 ms 5304 KB Output is correct
10 Correct 3396 ms 7248 KB Output is correct
11 Correct 3401 ms 7136 KB Output is correct
12 Correct 2931 ms 7068 KB Output is correct
13 Correct 3362 ms 7120 KB Output is correct
14 Correct 401 ms 3984 KB Output is correct
15 Correct 1259 ms 6536 KB Output is correct
16 Correct 3574 ms 7412 KB Output is correct
17 Correct 5294 ms 8828 KB Output is correct
18 Correct 5062 ms 8744 KB Output is correct
19 Correct 6882 ms 8744 KB Output is correct
20 Correct 5524 ms 9044 KB Output is correct
21 Correct 5500 ms 9004 KB Output is correct
22 Correct 6403 ms 9124 KB Output is correct
23 Execution timed out 9068 ms 16200 KB Time limit exceeded
24 Halted 0 ms 0 KB -