Submission #358997

#TimeUsernameProblemLanguageResultExecution timeMemory
358997hivakaramiDancing Elephants (IOI11_elephants)C++14
Compilation error
0 ms0 KiB
#include "elephants.h" #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 = 15e4 + 100; const int sq = 500; const ll mod = 1e9 + 7; const ll inf = 1e16; int n, len, q = 0, m = 0; int a[N], id[N]; vector<int> v[sq], tmp; int nx[sq][N], dp[sq][N]; //* void init(int N, int L, int X[]) { n = N; len = L; a = X; } //*/ void bld(int x) { int sz = v[x].size(); int pt = sz; for(int i = sz - 1; i >= 0; i--) { while(pt > 0 && v[x][pt-1] > v[x][i] + len) pt--; if(pt >= sz) { dp[x][i] = 1; nx[x][i] = v[x][i] + len + 1; } else { dp[x][i] = dp[x][pt] + 1; nx[x][i] = nx[x][pt]; } } } void build() { vector<pair<int, int>> vec; for(int i = 0; i < m; i++) v[i].clear(); for(int i = 0; i < n; i++) vec.push_back({a[i], i}); sort(vec.begin(), vec.end()); m = 0; for(int i = 0; i < n; i++) { if(v[m].size() == sq) bld(m++); v[m].push_back(vec[i].f); id[vec[i].s] = m; } bld(m++); } void del(int i) { tmp.clear(); int j = id[i]; bool fl = true; for(auto x : v[j]) { if(fl && x == a[i]) fl = false; else tmp.push_back(x); } v[j] = tmp; bld(j); } void add(int i, int y) { //cout << "add" << ' ' << i << ' ' << y << endl; tmp.clear(); int j = 0; while(j+1 < m && v[j+1][0] > y) j++; bool fl = false; for(auto x : v[j]) { if(!fl && x > y) { tmp.push_back(y); fl = true; } tmp.push_back(x); } if(!fl) tmp.push_back(y); v[j] = tmp; a[i] = y; id[i] = j; bld(j); } int get_ans() { int res = 0, pt = 0, c = v[0][0]; while(pt < m) { while(pt < m && v[pt].back() < c) pt++; if(pt >= m) break; int k = lower_bound(v[pt].begin(), v[pt].end(), c) - v[pt].begin(); res += dp[pt][k]; c = nx[pt][k]; } return res; } int update(int i, int y) { if(q%(sq-2) == 0) build(); q++; del(i); add(i, y); return get_ans(); } /* int main() { cin >> n >> len; for(int i = 0; i < n; i++) { cin >> a[i]; } int qu; cin >> qu; while(qu--) { int a, b; cin >> a >> b; //cout << "///////////" << endl; cout << update(a, b) << '\n'; /* for(int i = 0; i < m; i++) { for(auto x : v[i]) cout << x << ' '; cout << endl; } //*/ } return 0; } //*/

Compilation message (stderr)

elephants.cpp:181:3: warning: "/*" within comment [-Wcomment]
  181 |   /*
      |    
elephants.cpp: In function 'void init(int, int, int*)':
elephants.cpp:25:6: error: incompatible types in assignment of 'int*' to 'int [150100]'
   25 |  a = X;
      |      ^
elephants.cpp: At global scope:
elephants.cpp:190:2: error: expected declaration before '}' token
  190 |  }
      |  ^
elephants.cpp:192:2: error: expected unqualified-id before 'return'
  192 |  return 0;
      |  ^~~~~~
elephants.cpp:194:1: error: expected declaration before '}' token
  194 | }
      | ^