Submission #352344

#TimeUsernameProblemLanguageResultExecution timeMemory
352344hivakaramiDancing Elephants (IOI11_elephants)C++14
Compilation error
0 ms0 KiB
#include<bits/stdc++.h> using namespace std; typedef long long int ll; typedef long double ld; #define f first #define s second const int N = 1e5 + 5; const int sq = 500; const ll mod = 1e9 + 7; const ll inf = 1e16; int n, len, q = 0; vector<int> v[sq], tmp; int nx[sq][N], dp[sq][N], x[N]; map<int, int> cnt; /* void init(int N, int L, int X[]) { n = N; len = L; x = X; for(int i = 0; i < n; i++) cnt[x[i]]++; } //*/ void bld(int id) { //cout << "id : "<< id << endl; int m = v[id].size(); nx[id][m-1] = v[id][m-1] + len; dp[id][m-1] = 1; for(int i = m - 2; i >= 0; i--) { if(v[id][m-1] > v[id][i]+len) { auto it = upper_bound(v[id].begin(), v[id].end(), v[id][i]+len); int p = it - v[id].begin(); nx[id][i] = nx[id][p]; dp[id][i] = dp[id][p] + 1; } else { dp[id][i] = 1; nx[id][i] = v[id][i] + len; } } //for(int i = m-1; i >= 0; i--) //cout << nx[id][i] << ' ' << dp[id][i] << endl; } void build() { sort(x, x + n); n = unique(x, x+n) - x; for(int i = 0; i < sq; i++) v[i].clear(); int id = 0; for(int i = 0; i < n; i++) { v[id].push_back(x[i]); if(v[id].size() == sq) { bld(id); id++; } } if(v[id].size() != 0) bld(id); //cout << "////////" << endl; } void add(int k, bool b) { int id = 0; for(int i = 0; i < sq; i++) { if(v[i].size() != 0 && v[i][0] <= k) { id = i; break; } } //for(auto a : v[id]) //cout << a << ' '; //cout << endl; if(!b) { tmp = v[id]; v[id].clear(); for(auto y : tmp) { if(y != k) v[id].push_back(y); } } else { bool fl = false; tmp = v[id]; v[id].clear(); for(auto y : tmp) { if(y > k) { v[id].push_back(k); v[id].push_back(y); fl = true; } } if(!fl) v[id].push_back(k); } bld(id); } int update(int i, int y) { if(q%sq == 0) build(); q++; cnt[x[i]]--; if(cnt[x[i]] == 0) add(x[i], 0); x[i] = y; if(cnt[x[i]] == 0) add(x[i], 1); cnt[y]++; int j = 0, ans = 0; for(int i = 0; i < sq; i++) { if(j < v[i].size()) ans += dp[i][j]; if(v[i+1].empty()) break; j = upper_bound(v[i+1].begin(), v[i+1].end(), nx[i][j]) - v[i+1].begin(); } return ans; } /* int main() { cin >> n >> len; for(int i = 0; i < n; i++) { cin >> x[i]; cnt[x[i]]++; } int a, b; cin >> a >> b; cout << update(a, b) << endl; return 0; } */

Compilation message (stderr)

elephants.cpp: In function 'int update(int, int)':
elephants.cpp:159:8: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  159 |   if(j < v[i].size())
      |      ~~^~~~~~~~~~~~~
/tmp/cca192QK.o: In function `main':
grader.cpp:(.text.startup+0x23): undefined reference to `init(int, int, int*)'
collect2: error: ld returned 1 exit status