Submission #395872

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
395872	2021-04-29T05:04:58 Z	pure_mem	Game (IOI13_game)	C++14	Compilation error	0 ms	0 KB

game

#pragma GCC optimize("Ofast")

#include "game.h"
#include <iostream>
#include <algorithm>

#define ll long long
#define X first
#define Y second
#define MP make_pair

using namespace std;

const MAXN = 1e6;

ll gcd(ll x, ll y) {
	if(x < y)
		swap(x, y);
    while(y){
    	x %= y;
    	swap(x, y);
    }
    return x;
}

int n, m, dl, dr, ptr;

struct node{
	node* p[2] = {nullptr, nullptr};
	node* p1[2] = {nullptr, nullptr};
	ll val = 0;
	node* getp(int v);
	node* getp1(int v);
	void merge(int tl, int tr, node* L, node* R, int pos);
	void upd1(int tl, int tr, int pos, ll _val);
	ll get1(int tl, int tr, int l, int r);
	void upd(int tl, int tr, int pos, ll _val);
	ll get(int tl, int tr, int l, int r);
}root, baz[MAXN];

node* node::getp(int v){
	if(!p[v])
		p[v] = &baz[ptr++];
	return p[v];	
}
node* node::getp1(int v){
	if(!p1[v])
		p1[v] = &baz[ptr++];
	return p1[v];	
}

void node::merge(int tl, int tr, node* L, node* R, int pos){
   if(!L && !R)
   	return;
   if(tl == tr){
   	val = 0;
   	if(L)
   		val = gcd(L->val, val);
   	if(R)
   		val = gcd(R->val, val);
   	return;	
   }          
   int tm = (tl + tr) / 2;
   if(pos <= tm){
   	if(L)
   		L = L->p1[0];
   	if(R)
   		R = R->p1[0];
   	getp1(0)->merge(tl, tm, L, R, pos);
   }
   else{
   	if(L)
   		L = L->p1[1];
   	if(R)
   		R = R->p1[1];
       getp1(1)->merge(tm + 1, tr, L, R, pos);
   }
   val = 0;
   if(p1[0])
   	val = gcd(p1[0]->val, val);
   if(p1[1])
   	val = gcd(p1[1]->val, val);
   //cerr << tl << " " << tr << " " << val << " " << this << "s\n";
}
void node::upd1(int tl, int tr, int pos, ll _val){
   if(tl == tr)
   	return void(val = _val);
   int tm = (tl + tr) / 2;
   //cerr << tl << " s " << tr << "\n"; 
   if(pos <= tm)
   	getp1(0)->upd1(tl, tm, pos, _val);
   else
   	getp1(1)->upd1(tm + 1, tr, pos, _val);
   val = 0;
   if(p1[0])
   	val = gcd(p1[0]->val, val);
   if(p1[1])
   	val = gcd(p1[1]->val, val);
}
ll node::get1(int tl, int tr, int l, int r){
   if(tl > r || l > tr)
   	return 0;
   if(tl >= l && tr <= r)
   	return val;
   int tm = (tl + tr) / 2;
   return gcd((p1[0] ? p1[0]->get1(tl, tm, l, r): 0), (p1[1] ? p1[1]->get1(tm + 1, tr, l, r): 0));
}
void node::upd(int tl, int tr, int pos, ll _val){
   //cerr << tl << " " << tr << " b " << this << "\n";
   if(tl == tr){
   	return void(upd1(1, m, dl, _val));
   }
   int tm = (tl + tr) / 2;
   if(pos <= tm)
   	getp(0)->upd(tl, tm, pos, _val);
   else
   	getp(1)->upd(tm + 1, tr, pos, _val);
   merge(1, m, p[0], p[1], dl);	
}
ll node::get(int tl, int tr, int l, int r){
   if(tl > r || l > tr)
   	return 0;
   if(tl >= l && tr <= r)
   	return get1(1, m, dl, dr);
   int tm = (tl + tr) / 2;
   //cerr << tl << " " << tr << " " << left << " z " << right << "\n";
   return gcd((p[0] ? p[0]->get(tl, tm, l, r): 0), (p[1] ? p[1]->get(tm + 1, tr, l, r): 0));
}

void init(int R, int C) {
	n = R, m = C;    
}

void update(int P, int Q, ll K) {
//	cerr << "was1\n";
	dl = Q + 1;
	//cerr << P + 1 << " " << Q + 1 << "\n";
	root.upd(1, n, P + 1, K);
//	cerr << "was\n";	
}

long long calculate(int P, int Q, int U, int V) {
    /* ... */
    //cerr << "were\n";
    dl = Q + 1, dr = V + 1;
    //cerr << P + 1 << " " << U + 1 << " " << dl << " " << dr << "\n";
    ll tmp = root.get(1, n, P + 1, U + 1);
 //   cerr << tmp << "\n";
    return tmp;
}

Compilation message

game.cpp:14:7: error: 'MAXN' does not name a type
   14 | const MAXN = 1e6;
      |       ^~~~
game.cpp:39:12: error: 'MAXN' was not declared in this scope
   39 | }root, baz[MAXN];
      |            ^~~~
game.cpp: In member function 'node* node::getp(int)':
game.cpp:43:11: error: 'baz' was not declared in this scope
   43 |   p[v] = &baz[ptr++];
      |           ^~~
game.cpp: In member function 'node* node::getp1(int)':
game.cpp:48:12: error: 'baz' was not declared in this scope
   48 |   p1[v] = &baz[ptr++];
      |            ^~~