제출 #94592

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
94592		Retro3014	게임 (IOI13_game)	C++17	80 / 100	6801 ms	257024 KiB

game

#include "game.h"
#include <vector>
#include <stdio.h>
#include <algorithm>
#include <iostream>
#include <deque>

typedef long long ll;
using namespace std;


long long gcd2(long long X, long long Y) {
    long long tmp;
    while (X != Y && Y != 0) {
        tmp = X;
        X = Y;
        Y = tmp % Y;
    }
    return X;
}

struct SEG2{
	int s, e;
	int l=-1, r=-1;
	ll gcd = 0;
};
vector<SEG2> s2;

struct SEG1{
	int s, e;
	int l, r;
	vector<SEG2> seg2;
};
vector<SEG1> seg1;
int r, c;


void init(int R, int C) {
	r = R; c = C;
	seg1.push_back({0, R-1, -1, -1, s2});
}

int qq;
ll k;

void update2(int x, int y){
	//seg1[x].seg2[y].gcd = gcd2(seg1[x].seg2[y].gcd, K);
	if(seg1[x].seg2[y].s==seg1[x].seg2[y].e){
		seg1[x].seg2[y].gcd = k;
		return;
	}
	if(qq<=(seg1[x].seg2[y].s+seg1[x].seg2[y].e)/2){
		if(seg1[x].seg2[y].l==-1){
			seg1[x].seg2[y].l = seg1[x].seg2.size();
			SEG2 tmp; tmp.s=seg1[x].seg2[y].s; tmp.e=(seg1[x].seg2[y].s+seg1[x].seg2[y].e)/2; tmp.l=-1;tmp.r=-1;tmp.gcd=0;
			seg1[x].seg2.push_back(tmp);
		}
		update2(x, seg1[x].seg2[y].l);
		if(seg1[x].seg2[y].r==-1)	seg1[x].seg2[y].gcd = seg1[x].seg2[seg1[x].seg2[y].l].gcd;
		else	seg1[x].seg2[y].gcd = gcd2(seg1[x].seg2[seg1[x].seg2[y].l].gcd, seg1[x].seg2[seg1[x].seg2[y].r].gcd);
	}else{
		if(seg1[x].seg2[y].r==-1){
			seg1[x].seg2[y].r = seg1[x].seg2.size();
			SEG2 tmp; tmp.s=(seg1[x].seg2[y].s+seg1[x].seg2[y].e)/2+1; tmp.e=seg1[x].seg2[y].e; tmp.l=-1;tmp.r=-1;tmp.gcd=0;
			seg1[x].seg2.push_back(tmp);
		}
		update2(x, seg1[x].seg2[y].r);
		if(seg1[x].seg2[y].l==-1)	seg1[x].seg2[y].gcd = seg1[x].seg2[seg1[x].seg2[y].r].gcd;
		else	seg1[x].seg2[y].gcd = gcd2(seg1[x].seg2[seg1[x].seg2[y].l].gcd, seg1[x].seg2[seg1[x].seg2[y].r].gcd);
	}
}

int pp;

ll findg(int x, int y){
	if(y==-1)	return 0;
	if(seg1[x].seg2[y].s==seg1[x].seg2[y].e)	return seg1[x].seg2[y].gcd;
	if(qq<=(seg1[x].seg2[y].s+seg1[x].seg2[y].e)/2)		return findg(x, seg1[x].seg2[y].l);
	else	return findg(x, seg1[x].seg2[y].r);
}

void update1(int x){
	if(seg1[x].seg2.empty()){
		SEG2 tmp;tmp.s=0;tmp.e=c-1;tmp.l=-1;tmp.r=-1;tmp.gcd=0;
		seg1[x].seg2.push_back(tmp);
	}
	if(seg1[x].s==seg1[x].e){
		update2(x, 0);	return;
	}
	if(pp<=(seg1[x].s+seg1[x].e)/2){
		if(seg1[x].l==-1){
			seg1[x].l = seg1.size();
			seg1.push_back({seg1[x].s, (seg1[x].s+seg1[x].e)/2, -1, -1, s2});
		}
		update1(seg1[x].l);
		if(seg1[x].r!=-1 && !seg1[seg1[x].r].seg2.empty())	k = gcd2(k, findg(seg1[x].r, 0));
	}else{
		if(seg1[x].r==-1){
			seg1[x].r = seg1.size();
			seg1.push_back({(seg1[x].s+seg1[x].e)/2+1, seg1[x].e, -1, -1, s2});
		}
		update1(seg1[x].r);
		if(seg1[x].l!=-1 && !seg1[seg1[x].l].seg2.empty())	k = gcd2(k, findg(seg1[x].l, 0));
	}
	update2(x, 0);
}

void update(int P, int Q, long long K) {
	pp = P; qq = Q; k = K;
	update1(0);
}

int p, q, u, v;

ll calc2(int x, int y){
	if(y==-1)	return 0;
	if(seg1[x].seg2[y].s > v || seg1[x].seg2[y].e < q)	return 0;
	if(q <= seg1[x].seg2[y].s && seg1[x].seg2[y].e <= v)	return seg1[x].seg2[y].gcd;
	return gcd2(calc2(x, seg1[x].seg2[y].l), calc2(x, seg1[x].seg2[y].r));
}

ll calc1(int x){
	if(x==-1)	return 0;
	if(seg1[x].s>u || seg1[x].e<p)	return 0;
	if(p <= seg1[x].s && seg1[x].e <= u){
		if(seg1[x].seg2.empty())	return 0;
		else{
			return calc2(x, 0);
		}
	}
	return gcd2(calc1(seg1[x].l), calc1(seg1[x].r));
}

long long calculate(int P, int Q, int U, int V) {
    p = P; q = Q;
    u = U; v = V;
    return calc1(0);
}

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

grader.c: In function 'int main()':
grader.c:18:6: warning: variable 'res' set but not used [-Wunused-but-set-variable]
  int res;
      ^~~

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