oj.uz

답안 #94365

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
94365 2019-01-18T01:37:34 Z fjzzq2002 게임 (IOI13_game) C++14
10 / 100
 13000 ms 2832 KB 
#include "game.h"
#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
inline ull gcd(ull a,ull b)
{
	ull t;
	while(b)
		t=a%b,a=b,b=t;
	return a;
	/*
    #define ctz __builtin_ctzll
    int shift = ctz(a | b);
    b >>= ctz(b);
    while (a) {
        a >>= ctz(a);
        if (a < b) swap(a, b);
        a -= b;
    }
    return b << shift;
    #undef ctz*/
}

#define SS 2600003
int an=0,ch[SS][2],sz[SS],xx[SS],R;
ull vv[SS],ss[SS];
void upd(int x)
{
	sz[x]=1+sz[ch[x][0]]+sz[ch[x][1]];
	ss[x]=gcd(gcd(vv[x],ss[ch[x][0]]),ss[ch[x][1]]);
}
int merge(int a,int b)
{
	if(a&&b);else return a^b;
	if(sz[a]>sz[b])
	{
		ch[a][1]=merge(ch[a][1],b),upd(a);
		return a;
	}
	else
	{
		ch[b][0]=merge(a,ch[b][0]),upd(b);
		return b;
	}
}
void split(int x,int u,int& a,int& b)
{
//	cerr<<x<<","<<u<<","<<a<<","<<b<<"\n";
	if(x==0) {a=b=0; return;}
	if(xx[x]<=u)
		a=x, split(ch[a][1],u,ch[a][1],b), upd(a);
	else
		b=x, split(ch[b][0],u,a,ch[b][0]), upd(b);
}
void edt(int& u,int x,ull v)
{
//	cerr<<"E+\n";
	int A,B,C;
	split(u,x-1,A,B);
	split(B,x,B,C);
//	cerr<<"S\n";
	if(!B) B=++an,sz[B]=1,xx[B]=x;
	else assert(sz[B]==1);
	vv[B]=ss[B]=v;
	B=merge(B,C);
	u=merge(A,B);
//	cerr<<"E-\n";
}
ull qry(int& u,int l,int r)
{
	int A,B,C;
	split(u,l-1,A,B);
	split(B,r,B,C);
	ull rs=ss[B];
	B=merge(B,C);
	u=merge(A,B);
	return rs;
}

int seg_ch[SS][2],seg_ps[SS],sn=0,ro;
void edt(int& x,int l,int r,int p,int q,ull v)
{
//	cerr<<x<<"?\n";
	if(!x) x=++sn; edt(seg_ps[x],q,v);
	if(l==r) return;
	int m=(l+r)>>1;
	if(p<=m) edt(ch[x][0],l,m,p,q,v);
	else edt(ch[x][1],m+1,r,p,q,v);
}
ull qry(int x,int l,int r,int pl,int pr,int sl,int sr)
{
	if(r<pl||pr<l||!x||pl>pr) return 0;
	if(pl<=l&&r<=pr) return qry(seg_ps[x],sl,sr);
	int m=(l+r)>>1;
	return gcd(qry(ch[x][0],l,m,pl,pr,sl,sr),
	qry(ch[x][1],m+1,r,pl,pr,sl,sr));
}
ull t[233][233];
void init(int R_, int C_) {
	R=R_;
}

void update(int P, int Q, long long K) {
	t[P][Q]=K;
}

long long calculate(int P, int Q, int U, int V) {
	ull w=0;
	for(int x=P;x<=U;++x)
		for(int y=Q;y<=V;++y)
			w=gcd(w,t[x][y]);
	return w;
}

Compilation message

grader.c: In function 'int main()':
grader.c:18:6: warning: variable 'res' set but not used [-Wunused-but-set-variable]
  int res;
      ^~~
game.cpp: In function 'void edt(int&, int, int, int, int, ull)':
game.cpp:85:2: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
  if(!x) x=++sn; edt(seg_ps[x],q,v);
  ^~
game.cpp:85:17: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
  if(!x) x=++sn; edt(seg_ps[x],q,v);
                 ^~~

Subtask #1
10.0 / 10.0

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

Subtask #2
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 2 ms 380 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Execution timed out 13074 ms 2272 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #3
0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 504 KB Output is correct
3 Correct 2 ms 504 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 508 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 504 KB Output is correct
10 Correct 3 ms 504 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Execution timed out 13078 ms 2832 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 2 ms 504 KB Output is correct
3 Correct 2 ms 504 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 256 KB Output is correct
6 Correct 2 ms 504 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 504 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Execution timed out 13045 ms 2220 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 2 ms 504 KB Output is correct
3 Correct 2 ms 504 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 256 KB Output is correct
6 Correct 2 ms 504 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 508 KB Output is correct
10 Correct 2 ms 424 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Execution timed out 13060 ms 2024 KB Time limit exceeded
13 Halted 0 ms 0 KB -