oj.uz

Submission #448579

# Submission time Handle Problem Language Result Execution time Memory
448579 2021-07-30T20:50:19 Z SirCovidThe19th Dancing Elephants (IOI11_elephants) C++14
50 / 100
 713 ms 6044 KB 
#include <bits/stdc++.h>
using namespace std; 
 
#define ar2 array<int, 2>
#define lb(v, x) lower_bound(v.begin(), v.end(), x)-v.begin()
 
const int mx = 1.5e5+5, sq = 555, mBL = mx/sq+5;
 
int N, L, X[mx], R[mx], mxB, reset; vector<int> blk[mBL]; vector<ar2> dp[mBL]; map<int, int> mp;
 
void calc(int b){
    int sz = blk[b].size(); dp[b].clear(); dp[b].resize(sz);
    for (int i = sz-1, p = sz-1; i >= 0; i--){
        while (blk[b][p]-blk[b][i] > L) p--;
        dp[b][i] = (p == sz-1) ? ar2{1, blk[b][i]+L} : ar2{dp[b][p+1][0]+1, dp[b][p+1][1]};
    }
}
void build(){
    int b = 0; blk[b].clear();
    for (auto i : mp){
        if (blk[b].size() >= sq) blk[++b].clear();
        blk[b].push_back(i.first);
    }for (int i = 0; i <= mxB; i++) calc(i), R[i] = (i == mxB) ? 2e9 : blk[i].back();
}
void upd(int x, bool ins){
    int b = 0; while (x > R[b]) b++;  
    int p = lb(blk[b], x);
    ins ? blk[b].insert(blk[b].begin()+p, x) : blk[b].erase(blk[b].begin()+p);
    calc(b);
}
int query(){ 
    int ans = 0;
    for (int b = 0, x = -1; b <= mxB; b++){
        int p = lb(blk[b], x+1);
        if (p != blk[b].size()) x = dp[b][p][1], ans += dp[b][p][0];
    }return ans;
}
void init(int n, int l, int x[]){
    N = n; L = l; mxB = (N-1)/sq;  
    for (int i = 0; i < n; i++) X[i] = x[i], mp[X[i]]++;
    build();
}
int update(int i, int y){
    if (++reset == sq) build(), reset = 0;
    mp[X[i]]--; 
    if (!mp[X[i]]) upd(X[i], 0), mp.erase(X[i]);
    if (!mp[y]) upd(y, 1);
    mp[y]++; 
    X[i] = y; return query();
}

Compilation message

elephants.cpp: In function 'int query()':
elephants.cpp:35:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |         if (p != blk[b].size()) x = dp[b][p][1], ans += dp[b][p][0];
      |             ~~^~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 0 ms 332 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 0 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 0 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 287 ms 1828 KB Output is correct
8 Correct 321 ms 3316 KB Output is correct
9 Correct 406 ms 6044 KB Output is correct
10 Correct 308 ms 5808 KB Output is correct
11 Correct 327 ms 5700 KB Output is correct
12 Correct 713 ms 5956 KB Output is correct
13 Correct 309 ms 5576 KB Output is correct

Subtask #4
0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 0 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 287 ms 1828 KB Output is correct
8 Correct 321 ms 3316 KB Output is correct
9 Correct 406 ms 6044 KB Output is correct
10 Correct 308 ms 5808 KB Output is correct
11 Correct 327 ms 5700 KB Output is correct
12 Correct 713 ms 5956 KB Output is correct
13 Correct 309 ms 5576 KB Output is correct
14 Incorrect 65 ms 3792 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 332 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 0 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 287 ms 1828 KB Output is correct
8 Correct 321 ms 3316 KB Output is correct
9 Correct 406 ms 6044 KB Output is correct
10 Correct 308 ms 5808 KB Output is correct
11 Correct 327 ms 5700 KB Output is correct
12 Correct 713 ms 5956 KB Output is correct
13 Correct 309 ms 5576 KB Output is correct
14 Incorrect 65 ms 3792 KB Output isn't correct
15 Halted 0 ms 0 KB -