제출 #531876

#제출 시각아이디문제언어결과실행 시간메모리
531876Alex_tz307게임 (IOI13_game)C++17
100 / 100
6420 ms46656 KiB
#include <bits/stdc++.h> #include "game.h" using namespace std; const int mod = 1e9 + 9; mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); struct treapNode { treapNode* l; treapNode* r; int key, prior; int64_t val, gcd; }; using ptr = treapNode*; using pt = pair<ptr, ptr>; ptr NIL = new treapNode{nullptr, nullptr, 0, -1, 0, 0}; int64_t gcd2(int64_t X, int64_t Y) { int64_t tmp; while (X != Y && Y != 0) { tmp = X; X = Y; Y = tmp % Y; } return X; } void updateNode(ptr &x) { if (x != NIL) { x->gcd = gcd2(gcd2(x->l->gcd, x->val), x->r->gcd); } } pt split(ptr &x, int k) { if (x == NIL) { return {NIL, NIL}; } if (k < x->key) { pt p = split(x->l, k); x->l = p.second; updateNode(x); return {p.first, x}; } pt p = split(x->r, k); x->r = p.first; updateNode(x); return {x, p.second}; } ptr join(ptr x, ptr y) { if (x == NIL) { return y; } if (y == NIL) { return x; } if (y->prior < x->prior) { x->r = join(x->r, y); updateNode(x); return x; } y->l = join(x, y->l); updateNode(y); return y; } bool check(ptr &x, int k, int64_t v) { if (x == NIL) { return false; } if (x->key == k) { x->val = v; updateNode(x); return true; } if (k < x->key) { bool ret = check(x->l, k, v); updateNode(x); return ret; } else { bool ret = check(x->r, k, v); updateNode(x); return ret; } } ptr ins(ptr &x, int k, int64_t v) { if (check(x, k, v)) { return x; } pt p = split(x, k); ptr newNode = new treapNode{NIL, NIL, k, rng() % mod, v, v}; return join(join(p.first, newNode), p.second); } int64_t queryY(ptr &x, int st, int dr) { pt p1 = split(x, st - 1); pt p2 = split(p1.second, dr); int64_t ans = p2.first->gcd; p1.second = join(p2.first, p2.second); x = join(p1.first, p1.second); return ans; } struct sgtNode { ptr root; sgtNode* l; sgtNode* r; sgtNode() : root(NIL), l(nullptr), r(nullptr) {} } *root; void update(sgtNode* &x, int lx, int rx, int X, int Y, int64_t v) { if (!x) { x = new sgtNode(); } if (lx == rx) { x->root = ins(x->root, Y, v); return; } int mid = (lx + rx) / 2; if (X <= mid) { update(x->l, lx, mid, X, Y, v); } else { update(x->r, mid + 1, rx, X, Y, v); } int64_t gcd = 0; if (x->l) { gcd = queryY(x->l->root, Y, Y); } if (x->r) { gcd = gcd2(gcd, queryY(x->r->root, Y, Y)); } x->root = ins(x->root, Y, gcd); } int64_t queryX(sgtNode* &x, int lx, int rx, int x1, int x2, int y1, int y2) { if (!x) { return 0; } if (x1 <= lx && rx <= x2) { return queryY(x->root, y1, y2); } int mid = (lx + rx) / 2; int64_t ans = 0; if (x1 <= mid) { ans = gcd2(ans, queryX(x->l, lx, mid, x1, x2, y1, y2)); } if (mid < x2) { ans = gcd2(ans, queryX(x->r, mid + 1, rx, x1, x2, y1, y2)); } return ans; } int N; void init(int R, int C) { N = R; } void update(int P, int Q, long long K) { update(root, 0, N - 1, P, Q, K); } long long calculate(int P, int Q, int U, int V) { return queryX(root, 0, N - 1, P, U, Q, V); }

컴파일 시 표준 에러 (stderr) 메시지

game.cpp: In function 'treapNode* ins(treapNode*&, int, int64_t)':
game.cpp:94:50: warning: narrowing conversion of '(rng.std::mersenne_twister_engine<long unsigned int, 32, 624, 397, 31, 2567483615, 11, 4294967295, 7, 2636928640, 15, 4022730752, 18, 1812433253>::operator()() % ((std::mersenne_twister_engine<long unsigned int, 32, 624, 397, 31, 2567483615, 11, 4294967295, 7, 2636928640, 15, 4022730752, 18, 1812433253>::result_type)((int)mod)))' from 'std::mersenne_twister_engine<long unsigned int, 32, 624, 397, 31, 2567483615, 11, 4294967295, 7, 2636928640, 15, 4022730752, 18, 1812433253>::result_type' {aka 'long unsigned int'} to 'int' [-Wnarrowing]
   94 |   ptr newNode = new treapNode{NIL, NIL, k, rng() % mod, v, v};
      |                                            ~~~~~~^~~~~
#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...