oj.uz

Submission #769248

# Submission time Handle Problem Language Result Execution time Memory
769248 2023-06-29T10:47:46 Z Dan4Life Dancing Elephants (IOI11_elephants) C++17
97 / 100
 9000 ms 16816 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(){
        for(int i = sz(V)-1; i>=0; i--){
            int pos = lb(begin(V)+i,end(V),V[i]+L+1)-begin(V);
            if(pos==sz(V)) V2[i]=ar({1,V[i]+L+1});
            else V2[i]=ar({V2[pos][0]+1,V2[pos][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;
 
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[i]=Block(V3), bl.erase(begin(bl)+j);
} 
 
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]); 
    if(i) combine(i-1,i);
    else if(i<sz(bl)-1) 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 'void combine(int, int)':
elephants.cpp:38:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   38 |     if(SZ>B) return; vector<int> V3(SZ);
      |     ^~
elephants.cpp:38:22: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   38 |     if(SZ>B) return; 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 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 0 ms 340 KB Output is correct
3 Correct 1 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 1 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 812 ms 3788 KB Output is correct
8 Correct 1116 ms 4220 KB Output is correct
9 Correct 4756 ms 5424 KB Output is correct
10 Correct 3653 ms 7184 KB Output is correct
11 Correct 3610 ms 7140 KB Output is correct
12 Correct 3131 ms 7064 KB Output is correct
13 Correct 3612 ms 7220 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 1 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 812 ms 3788 KB Output is correct
8 Correct 1116 ms 4220 KB Output is correct
9 Correct 4756 ms 5424 KB Output is correct
10 Correct 3653 ms 7184 KB Output is correct
11 Correct 3610 ms 7140 KB Output is correct
12 Correct 3131 ms 7064 KB Output is correct
13 Correct 3612 ms 7220 KB Output is correct
14 Correct 601 ms 4212 KB Output is correct
15 Correct 1514 ms 6544 KB Output is correct
16 Correct 4112 ms 7348 KB Output is correct
17 Correct 5754 ms 8804 KB Output is correct
18 Correct 5740 ms 8748 KB Output is correct
19 Correct 6781 ms 8832 KB Output is correct
20 Correct 5890 ms 8968 KB Output is correct
21 Correct 6068 ms 9088 KB Output is correct
22 Correct 7004 ms 9072 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 1 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 812 ms 3788 KB Output is correct
8 Correct 1116 ms 4220 KB Output is correct
9 Correct 4756 ms 5424 KB Output is correct
10 Correct 3653 ms 7184 KB Output is correct
11 Correct 3610 ms 7140 KB Output is correct
12 Correct 3131 ms 7064 KB Output is correct
13 Correct 3612 ms 7220 KB Output is correct
14 Correct 601 ms 4212 KB Output is correct
15 Correct 1514 ms 6544 KB Output is correct
16 Correct 4112 ms 7348 KB Output is correct
17 Correct 5754 ms 8804 KB Output is correct
18 Correct 5740 ms 8748 KB Output is correct
19 Correct 6781 ms 8832 KB Output is correct
20 Correct 5890 ms 8968 KB Output is correct
21 Correct 6068 ms 9088 KB Output is correct
22 Correct 7004 ms 9072 KB Output is correct
23 Execution timed out 9012 ms 16816 KB Time limit exceeded
24 Halted 0 ms 0 KB -