답안 #99097 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
99097	2019-02-28T14:51:30 Z	figter001	게임 (IOI13_game)	C++14	37 / 100	13000 ms	131188 KB

game

#include "game.h"
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
const int N = 1e5+50;
const ll oo = 1e18;
const ll mod = 1e9+7;

ll seg2[11][4*N];
int c,type,ro,up,dw;

struct node{
    ll sub[4500];
}seg[4500];

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

ll l,r,val,cur,in;

void update2(int n,int s,int e){
    if(s > cur || e < cur)return;
    if(s == e){
        seg[in].sub[n] = val;
        return;
    }
    update2(n*2,s,(s+e)/2);
    update2(n*2+1,(s+e)/2+1,e);
    seg[in].sub[n] = gcd2(seg[in].sub[n*2],seg[in].sub[n*2+1]);
}

void merge(int n,int s,int e){
    if(s == e){
        seg[in].sub[n] = gcd2(seg[in*2].sub[n],seg[in*2+1].sub[n]);
        return;
    }
    merge(n*2,s,(s+e)/2);
    merge(n*2+1,(s+e)/2+1,e);
    seg[in].sub[n] = gcd2(seg[in].sub[n*2],seg[in].sub[n*2+1]);
}

void update1(int n,int s,int e){
    if(s > r || e < l)return;
    if(s == e){
        if(type){
            in = n;
            update2(1,1,ro);
        }else seg2[cur][n] = val;
        return;
    }
    update1(n*2,s,(s+e)/2);
    update1(n*2+1,(s+e)/2+1,e);
    if(type){
        in = n;
        merge(1,1,ro);
    }else seg2[cur][n] = gcd2(seg2[cur][n*2],seg2[cur][n*2+1]);
}

int l1,r1;
ll get1(int n,int s,int e){
    if(s > r1 || e < l1)return 0;
    if(s >= l1 && e <= r1)return seg[in].sub[n];
    return gcd2(get1(n*2,s,(s+e)/2),get1(n*2+1,(s+e)/2+1,e));
}

ll get(int n,int s,int e){
    if(s > r || e < l)return 0;
    if(s >= l && e <= r){
        if(type){
            in = n;
            l1 = up;
            r1 = dw;
            //cout << in << ' ' << up << ' ' << dw << endl;
            return get1(1,1,ro);
        }
        else return seg2[cur][n];
    }
    return gcd2(get(n*2,s,(s+e)/2),get(n*2+1,(s+e)/2+1,e));
}

void init(int R, int C) {
    type = R>10;
    c=C;
    ro=R;
}

void update(int P, int Q, long long K) {
    Q++;
    P++;
    l = r = Q;
    val = K;
    cur = P;
    update1(1,1,c);
}

long long calculate(int P, int Q, int U, int V) {
    l = Q+1;
    r = V+1;
    ll ans = 0;
    up = P+1;
    dw = U+1;
    if(type)ans = get(1,1,c);
    else{
        for(int i=P+1;i<=U+1;i++){
            cur = i;
            ans = gcd2(ans,get(1,1,c));
        }
    }
    return ans;
}

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;
      ^~~

Subtask #1
10.0 / 10.0

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

Subtask #2
27.0 / 27.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	384 KB	Output is correct
2	Correct	2 ms	384 KB	Output is correct
3	Correct	3 ms	384 KB	Output is correct
4	Correct	1546 ms	20808 KB	Output is correct
5	Correct	814 ms	21116 KB	Output is correct
6	Correct	1383 ms	21752 KB	Output is correct
7	Correct	1426 ms	21388 KB	Output is correct
8	Correct	1163 ms	19988 KB	Output is correct
9	Correct	1368 ms	21676 KB	Output is correct
10	Correct	1177 ms	21112 KB	Output is correct
11	Correct	2 ms	384 KB	Output is correct

Subtask #3
0 / 26.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	384 KB	Output is correct
2	Correct	5 ms	1280 KB	Output is correct
3	Correct	5 ms	1280 KB	Output is correct
4	Correct	2 ms	384 KB	Output is correct
5	Correct	3 ms	384 KB	Output is correct
6	Correct	5 ms	1280 KB	Output is correct
7	Correct	2 ms	384 KB	Output is correct
8	Correct	3 ms	384 KB	Output is correct
9	Correct	5 ms	1280 KB	Output is correct
10	Correct	4 ms	896 KB	Output is correct
11	Correct	3 ms	896 KB	Output is correct
12	Correct	3585 ms	43928 KB	Output is correct
13	Correct	5051 ms	37644 KB	Output is correct
14	Correct	3608 ms	5576 KB	Output is correct
15	Correct	8932 ms	106044 KB	Output is correct
16	Correct	12276 ms	129980 KB	Output is correct
17	Correct	6173 ms	116328 KB	Output is correct
18	Execution timed out	13044 ms	129580 KB	Time limit exceeded
19	Halted	0 ms	0 KB	-

Subtask #4
0 / 17.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	384 KB	Output is correct
2	Correct	5 ms	1280 KB	Output is correct
3	Correct	5 ms	1280 KB	Output is correct
4	Correct	2 ms	384 KB	Output is correct
5	Correct	2 ms	384 KB	Output is correct
6	Correct	6 ms	1280 KB	Output is correct
7	Correct	2 ms	384 KB	Output is correct
8	Correct	3 ms	512 KB	Output is correct
9	Correct	5 ms	1280 KB	Output is correct
10	Correct	4 ms	896 KB	Output is correct
11	Correct	3 ms	896 KB	Output is correct
12	Correct	1650 ms	20964 KB	Output is correct
13	Correct	698 ms	21368 KB	Output is correct
14	Correct	1281 ms	21688 KB	Output is correct
15	Correct	1452 ms	21496 KB	Output is correct
16	Correct	1170 ms	19940 KB	Output is correct
17	Correct	1353 ms	21456 KB	Output is correct
18	Correct	1158 ms	20968 KB	Output is correct
19	Correct	3650 ms	44048 KB	Output is correct
20	Correct	4834 ms	37580 KB	Output is correct
21	Correct	3427 ms	5616 KB	Output is correct
22	Correct	7903 ms	106356 KB	Output is correct
23	Correct	12050 ms	130052 KB	Output is correct
24	Correct	5893 ms	116324 KB	Output is correct
25	Execution timed out	13036 ms	130424 KB	Time limit exceeded
26	Halted	0 ms	0 KB	-

Subtask #5
0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	384 KB	Output is correct
2	Correct	6 ms	1280 KB	Output is correct
3	Correct	7 ms	1280 KB	Output is correct
4	Correct	2 ms	384 KB	Output is correct
5	Correct	3 ms	460 KB	Output is correct
6	Correct	2 ms	1280 KB	Output is correct
7	Correct	2 ms	384 KB	Output is correct
8	Correct	2 ms	384 KB	Output is correct
9	Correct	6 ms	1280 KB	Output is correct
10	Correct	4 ms	896 KB	Output is correct
11	Correct	2 ms	896 KB	Output is correct
12	Correct	1602 ms	20868 KB	Output is correct
13	Correct	800 ms	21180 KB	Output is correct
14	Correct	1254 ms	21720 KB	Output is correct
15	Correct	1347 ms	21500 KB	Output is correct
16	Correct	1155 ms	19908 KB	Output is correct
17	Correct	1350 ms	21624 KB	Output is correct
18	Correct	1199 ms	21120 KB	Output is correct
19	Correct	3720 ms	43872 KB	Output is correct
20	Correct	4915 ms	37600 KB	Output is correct
21	Correct	3184 ms	5600 KB	Output is correct
22	Correct	8163 ms	105948 KB	Output is correct
23	Correct	12485 ms	129828 KB	Output is correct
24	Correct	6230 ms	116032 KB	Output is correct
25	Execution timed out	13045 ms	131188 KB	Time limit exceeded
26	Halted	0 ms	0 KB	-

답안 #99097

Compilation message

Subtask #1 10.0 / 10.0

Subtask #2 27.0 / 27.0

Subtask #3 0 / 26.0

Subtask #4 0 / 17.0

Subtask #5 0 / 20.0

Subtask #1
10.0 / 10.0

Subtask #2
27.0 / 27.0

Subtask #3
0 / 26.0

Subtask #4
0 / 17.0

Subtask #5
0 / 20.0