Submission #765242

#	Time	Username	Problem	Language	Result	Execution time	Memory
765242		NothingXD	Game (IOI13_game)	C++17	100 / 100	3054 ms	100164 KiB

game

#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++){
      |                  ~~^~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 27 / 27
• Subtask 3: 26 / 26
• Subtask 4: 17 / 17
• Subtask 5: 20 / 20