Submission #765242

#TimeUsernameProblemLanguageResultExecution timeMemory
765242NothingXDGame (IOI13_game)C++17
100 / 100
3054 ms100164 KiB
#include "game.h" #include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int,int> pii; typedef pair<ll,ll> pll; typedef double ld; typedef complex<ld> point; void debug_out(){cerr << endl;} template<typename Head, typename... Tail> void debug_out(Head H, Tail... T){ cout << H << ' '; debug_out(T...); } #define debug(...) cerr << "(" << #__VA_ARGS__ << "): ", debug_out(__VA_ARGS__) #define F first #define S second #define all(x) x.begin(), x.end() #define MP(x, y) make_pair(x, y) const int maxn = 3e5 + 10; vector<ll> seg[maxn << 2]; vector<pll> val[maxn << 2]; void build(vector<ll> &seg, vector<pll> &val, int v, int l, int r){ if (l + 1 == r){ seg[v] = val[l].S; return; } int mid = (l + r) >> 1; int lc = v << 1; int rc = lc | 1; build(seg, val, lc, l, mid); build(seg, val, rc, mid, r); seg[v] = gcd(seg[lc], seg[rc]); } void change(vector<ll> &seg, int v, int l, int r, int idx, ll val){ if (idx < l || r <= idx) return; if (l + 1 == r){ seg[v] = val; return; } int mid = (l + r) >> 1; int lc = v << 1; int rc = lc | 1; change(seg, lc, l, mid, idx, val); change(seg, rc, mid, r, idx, val); seg[v] = gcd(seg[lc], seg[rc]); } ll get(vector<ll> &seg, int v, int l, int r, int ql, int qr){ if (qr <= l || r <= ql) return 0; if (ql <= l && r <= qr) return seg[v]; int mid = (l + r) >> 1; int lc = v << 1; int rc = lc | 1; return gcd(get(seg, lc, l, mid, ql, qr), get(seg, rc, mid, r, ql, qr)); } vector<pll> num[maxn]; void d2build(int v, int l, int r){ val[v].clear(); if (l + 1 == r){ for (auto x: num[l]) val[v].push_back(x); } else{ int mid = (l + r) >> 1; int lc = v << 1; int rc = lc | 1; d2build(lc, l, mid); d2build(rc, mid, r); int ptl = 0, ptr = 0; while(ptl < val[lc].size() || ptr < val[rc].size()){ if (ptr == val[rc].size() || (ptl < val[lc].size() && val[lc][ptl] < val[rc][ptr])){ val[v].push_back(val[lc][ptl]); ptl++; } else{ val[v].push_back(val[rc][ptr]); ptr++; } } } seg[v].resize(4 * val[v].size() + 1); build(seg[v], val[v], 1, 0, val[v].size()); } void d2change(int v, int l, int r, int idx, ll ptr, ll prval, ll nwval){ if (idx < l || r <= idx) return; int idx2 = lower_bound(all(val[v]), MP(ptr, prval)) - val[v].begin(); val[v][idx2].S = nwval; change(seg[v], 1, 0, val[v].size(), idx2, nwval); if (l + 1 == r) return; int mid = (l + r) >> 1; int lc = v << 1; int rc = lc | 1; d2change(lc, l, mid, idx, ptr, prval, nwval); d2change(rc, mid, r, idx, ptr, prval, nwval); } ll d2get(int v, int l, int r, int qu, int qd, ll ql, ll qr){ if (qd <= l || r <= qu) return 0; if (qu <= l && r <= qd){ int L = lower_bound(all(val[v]), MP(ql, 0ll)) - val[v].begin(); int R = lower_bound(all(val[v]), MP(qr, 0ll)) - val[v].begin(); return get(seg[v], 1, 0, val[v].size(), L, R); } int mid = (l + r) >> 1; int lc = v << 1; int rc = lc | 1; return gcd(d2get(lc, l, mid, qu, qd, ql, qr), d2get(rc, mid, r, qu, qd, ql, qr)); } const int sq = 1200; vector<pair<pii,ll>> p1, p2; vector<int> numx; void init(int R, int C) { // ok :/ } void reset(){ for (int i = 0; i < numx.size(); i++) num[i].clear(); numx.clear(); for (auto x: p2) p1.push_back(x); sort(all(p1)); p2.clear(); int ptr = 0; numx.push_back(p1[0].F.F); num[0].push_back(MP(p1[0].F.S, p1[0].S)); for (int i = 1; i < p1.size(); i++){ if (p1[i].F.F != p1[i-1].F.F){ ptr++; numx.push_back(p1[i].F.F); } num[ptr].push_back(MP(p1[i].F.S, p1[i].S)); } d2build(1, 0, numx.size()); } void update(int P, int Q, long long K) { int idx = lower_bound(all(p1), MP(MP(P,Q), 0ll)) - p1.begin(); if (idx != p1.size() && p1[idx].F == MP(P,Q)){ int idx2 = lower_bound(all(numx), P) - numx.begin(); d2change(1, 0, numx.size(), idx2, Q, p1[idx].S, K); p1[idx].S = K; return; } for (int i = 0; i < p2.size(); i++){ if (p2[i].F == MP(P, Q)){ p2[i].S = K; return; } } p2.push_back(MP(MP(P, Q), K)); if (p2.size() == sq) reset(); } long long calculate(int P, int Q, int U, int V) { int l = lower_bound(all(numx), P) - numx.begin(); int r = lower_bound(all(numx), U+1) - numx.begin(); ll res = d2get(1, 0, numx.size(), l, r, Q, V+1); for (auto [x, y]: p2){ if (P <= x.F && x.F <= U && Q <= x.S && x.S <= V) res = gcd(res, y); } return res; }

Compilation message (stderr)

game.cpp: In function 'void d2build(int, int, int)':
game.cpp:82:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   82 |   while(ptl < val[lc].size() || ptr < val[rc].size()){
      |         ~~~~^~~~~~~~~~~~~~~~
game.cpp:82:37: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   82 |   while(ptl < val[lc].size() || ptr < val[rc].size()){
      |                                 ~~~~^~~~~~~~~~~~~~~~
game.cpp:83:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   83 |    if (ptr == val[rc].size() || (ptl < val[lc].size() && val[lc][ptl] < val[rc][ptr])){
      |        ~~~~^~~~~~~~~~~~~~~~~
game.cpp:83:38: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   83 |    if (ptr == val[rc].size() || (ptl < val[lc].size() && val[lc][ptl] < val[rc][ptr])){
      |                                  ~~~~^~~~~~~~~~~~~~~~
game.cpp: In function 'void reset()':
game.cpp:134:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  134 |  for (int i = 0; i < numx.size(); i++) num[i].clear();
      |                  ~~^~~~~~~~~~~~~
game.cpp:142:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  142 |  for (int i = 1; i < p1.size(); i++){
      |                  ~~^~~~~~~~~~~
game.cpp: In function 'void update(int, int, long long int)':
game.cpp:154:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  154 |  if (idx != p1.size() && p1[idx].F == MP(P,Q)){
      |      ~~~~^~~~~~~~~~~~
game.cpp:160:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  160 |  for (int i = 0; i < p2.size(); i++){
      |                  ~~^~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...