oj.uz

답안 #395876

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
395876 2021-04-29T05:08:12 Z pure_mem 게임 (IOI13_game) C++14
63 / 100
 1693 ms 256004 KB 
#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 int MAXN = 1e7;

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;
}

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 1 ms 204 KB Output is correct

Subtask #2
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 574 ms 14712 KB Output is correct
5 Correct 427 ms 15072 KB Output is correct
6 Correct 482 ms 11924 KB Output is correct
7 Correct 536 ms 11692 KB Output is correct
8 Correct 404 ms 7856 KB Output is correct
9 Correct 530 ms 11772 KB Output is correct
10 Correct 511 ms 11420 KB Output is correct
11 Correct 1 ms 204 KB Output is correct

Subtask #3
26.0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 2 ms 332 KB Output is correct
3 Correct 1 ms 420 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 918 ms 18704 KB Output is correct
13 Correct 1421 ms 7388 KB Output is correct
14 Correct 335 ms 896 KB Output is correct
15 Correct 1671 ms 10560 KB Output is correct
16 Correct 216 ms 22412 KB Output is correct
17 Correct 810 ms 13788 KB Output is correct
18 Correct 1428 ms 22664 KB Output is correct
19 Correct 1217 ms 22776 KB Output is correct
20 Correct 1136 ms 22204 KB Output is correct
21 Correct 1 ms 204 KB Output is correct

Subtask #4
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 208 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 574 ms 14616 KB Output is correct
13 Correct 434 ms 15132 KB Output is correct
14 Correct 485 ms 11904 KB Output is correct
15 Correct 564 ms 11800 KB Output is correct
16 Correct 410 ms 7912 KB Output is correct
17 Correct 552 ms 11816 KB Output is correct
18 Correct 503 ms 11340 KB Output is correct
19 Correct 917 ms 18548 KB Output is correct
20 Correct 1450 ms 7344 KB Output is correct
21 Correct 290 ms 964 KB Output is correct
22 Correct 1693 ms 10572 KB Output is correct
23 Correct 227 ms 22472 KB Output is correct
24 Correct 807 ms 13800 KB Output is correct
25 Correct 1415 ms 22832 KB Output is correct
26 Correct 1227 ms 22916 KB Output is correct
27 Correct 1173 ms 22212 KB Output is correct
28 Runtime error 650 ms 256004 KB Execution killed with signal 9
29 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 591 ms 14928 KB Output is correct
13 Correct 438 ms 15140 KB Output is correct
14 Correct 497 ms 11996 KB Output is correct
15 Correct 580 ms 11780 KB Output is correct
16 Correct 379 ms 7868 KB Output is correct
17 Correct 555 ms 11908 KB Output is correct
18 Correct 510 ms 11608 KB Output is correct
19 Correct 973 ms 18688 KB Output is correct
20 Correct 1408 ms 7440 KB Output is correct
21 Correct 320 ms 1060 KB Output is correct
22 Correct 1679 ms 10780 KB Output is correct
23 Correct 230 ms 22468 KB Output is correct
24 Correct 922 ms 13948 KB Output is correct
25 Correct 1590 ms 22836 KB Output is correct
26 Correct 1332 ms 23180 KB Output is correct
27 Correct 1209 ms 22436 KB Output is correct
28 Runtime error 628 ms 256004 KB Execution killed with signal 9
29 Halted 0 ms 0 KB -