답안 #19052 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
19052	2016-02-17T11:42:54 Z	tlwpdus	게임 (IOI13_game)	C++	63 / 100	3327 ms	256000 KB

game

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

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

typedef long long ll;

int R, C;

struct node {
    node *l, *r;
    ll val;
    node() {
        l=r=NULL;
        val = 0;
    }
    void update(int idx, ll num, int s=0, int e=R-1) {
        if (s==e) {
            val = num;
            return;
        }
        int m = (s+e)>>1;
        if (m<idx) {
            if (!r) r=new node();
            r->update(idx,num,m+1,e);
        }
        else {
            if (!l) l=new node();
            l->update(idx,num,s,m);
        }
        val = gcd2((l)?l->val:0,(r)?r->val:0);
    }
    ll query(int S, int E, int s=0, int e=R-1) {
        if (s>E||S>e) return 0;
        if (S<=s&&e<=E) {
            return val;
        }
        int m = (s+e)>>1;
        return gcd2((l)?l->query(S,E,s,m):0,(r)?r->query(S,E,m+1,e):0);
    }
};

void hap(node *a, node *b, node *c, int idx, int s, int e) { // a+b->c
    if (s==e) {
        c->val = gcd2(a->val,b->val);
        return;
    }
    int m = (s+e)>>1;
    if (m<idx) {
        if (!a->r) a->r=new node();
        if (!b->r) b->r=new node();
        if (!c->r) c->r=new node();
        hap(a->r,b->r,c->r,idx,m+1,e);
    }
    else {
        if (!a->l) a->l=new node();
        if (!b->l) b->l=new node();
        if (!c->l) c->l=new node();
        hap(a->l,b->l,c->l,idx,s,m);
    }
    c->val = gcd2(a->val,b->val);
}

struct segnode {
    segnode *l, *r;
    node *root;
    segnode() {
        l=r=NULL;
        root=new node();
    }
    void update(int idx, int idy, ll num, int s=0, int e=C-1) {
        if (s==e) {
            root->update(idx,num);
            return;
        }
        int m = (s+e)>>1;
        if (!r) r=new segnode();
        if (!l) l=new segnode();
        if (m<idy) {
            r->update(idx,idy,num,m+1,e);
        }
        else {
            l->update(idx,idy,num,s,m);
        }
        hap(l->root,r->root,root,idx,0,R-1);
    }
    ll query(int p, int q, int u, int v, int s=0, int e=C-1) {
        if (s>v||q>e) return 0;
        if (q<=s&&e<=v) {
            return root->query(p,u);
        }
        int m = (s+e)>>1;
        return gcd2((l)?l->query(p,q,u,v,s,m):0,(r)?r->query(p,q,u,v,m+1,e):0);
    }
} seg;

void init(int r, int c) {
    R=r;
    C=c;
}

void update(int P, int Q, long long K) {
    seg.update(P,Q,K);
}

long long calculate(int P, int Q, int U, int V) {
    return seg.query(P,Q,U,V);
}

Subtask #1
10.0 / 10.0

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

Subtask #2
27.0 / 27.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	1284 KB	Output is correct
2	Correct	0 ms	1284 KB	Output is correct
3	Correct	0 ms	1284 KB	Output is correct
4	Correct	887 ms	17388 KB	Output is correct
5	Correct	755 ms	17388 KB	Output is correct
6	Correct	1100 ms	17784 KB	Output is correct
7	Correct	1223 ms	17784 KB	Output is correct
8	Correct	747 ms	10788 KB	Output is correct
9	Correct	1155 ms	17784 KB	Output is correct
10	Correct	1071 ms	17652 KB	Output is correct
11	Correct	0 ms	1284 KB	Output is correct

Subtask #3
26.0 / 26.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	1284 KB	Output is correct
2	Correct	0 ms	1416 KB	Output is correct
3	Correct	1 ms	1416 KB	Output is correct
4	Correct	0 ms	1284 KB	Output is correct
5	Correct	0 ms	1284 KB	Output is correct
6	Correct	1 ms	1416 KB	Output is correct
7	Correct	0 ms	1284 KB	Output is correct
8	Correct	0 ms	1284 KB	Output is correct
9	Correct	0 ms	1416 KB	Output is correct
10	Correct	0 ms	1284 KB	Output is correct
11	Correct	0 ms	1284 KB	Output is correct
12	Correct	1378 ms	19368 KB	Output is correct
13	Correct	2723 ms	8808 KB	Output is correct
14	Correct	536 ms	1416 KB	Output is correct
15	Correct	3322 ms	13164 KB	Output is correct
16	Correct	304 ms	29664 KB	Output is correct
17	Correct	1581 ms	17916 KB	Output is correct
18	Correct	2436 ms	29532 KB	Output is correct
19	Correct	2152 ms	29664 KB	Output is correct
20	Correct	2006 ms	29532 KB	Output is correct
21	Correct	0 ms	1284 KB	Output is correct

Subtask #4
0.0 / 17.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	1284 KB	Output is correct
2	Correct	0 ms	1416 KB	Output is correct
3	Correct	0 ms	1416 KB	Output is correct
4	Correct	0 ms	1284 KB	Output is correct
5	Correct	0 ms	1284 KB	Output is correct
6	Correct	0 ms	1416 KB	Output is correct
7	Correct	0 ms	1284 KB	Output is correct
8	Correct	0 ms	1284 KB	Output is correct
9	Correct	0 ms	1416 KB	Output is correct
10	Correct	0 ms	1284 KB	Output is correct
11	Correct	0 ms	1284 KB	Output is correct
12	Correct	883 ms	17388 KB	Output is correct
13	Correct	748 ms	17388 KB	Output is correct
14	Correct	1088 ms	17784 KB	Output is correct
15	Correct	1218 ms	17784 KB	Output is correct
16	Correct	768 ms	10788 KB	Output is correct
17	Correct	1193 ms	17784 KB	Output is correct
18	Correct	1069 ms	17652 KB	Output is correct
19	Correct	1389 ms	19368 KB	Output is correct
20	Correct	2714 ms	8808 KB	Output is correct
21	Correct	490 ms	1416 KB	Output is correct
22	Correct	3327 ms	13164 KB	Output is correct
23	Correct	326 ms	29664 KB	Output is correct
24	Correct	1563 ms	17916 KB	Output is correct
25	Correct	2496 ms	29532 KB	Output is correct
26	Correct	2175 ms	29664 KB	Output is correct
27	Correct	2018 ms	29532 KB	Output is correct
28	Memory limit exceeded	692 ms	256000 KB	Memory limit exceeded
29	Halted	0 ms	0 KB	-

Subtask #5
0.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	1284 KB	Output is correct
2	Correct	2 ms	1416 KB	Output is correct
3	Correct	0 ms	1416 KB	Output is correct
4	Correct	0 ms	1284 KB	Output is correct
5	Correct	0 ms	1284 KB	Output is correct
6	Correct	1 ms	1416 KB	Output is correct
7	Correct	0 ms	1284 KB	Output is correct
8	Correct	0 ms	1284 KB	Output is correct
9	Correct	0 ms	1416 KB	Output is correct
10	Correct	0 ms	1284 KB	Output is correct
11	Correct	0 ms	1284 KB	Output is correct
12	Correct	889 ms	17388 KB	Output is correct
13	Correct	779 ms	17388 KB	Output is correct
14	Correct	1104 ms	17784 KB	Output is correct
15	Correct	1255 ms	17784 KB	Output is correct
16	Correct	788 ms	10788 KB	Output is correct
17	Correct	1199 ms	17784 KB	Output is correct
18	Correct	1081 ms	17652 KB	Output is correct
19	Correct	1371 ms	19368 KB	Output is correct
20	Correct	2717 ms	8808 KB	Output is correct
21	Correct	502 ms	1416 KB	Output is correct
22	Correct	3309 ms	13164 KB	Output is correct
23	Correct	287 ms	29664 KB	Output is correct
24	Correct	1659 ms	17916 KB	Output is correct
25	Correct	2588 ms	29532 KB	Output is correct
26	Correct	2264 ms	29664 KB	Output is correct
27	Incorrect	1976 ms	29532 KB	Output isn't correct - wrong output format : File not found: "/var/www/temp/19052/outputsWG5_1"
28	Halted	0 ms	0 KB	-
29	Halted	0 ms	0 KB	-

답안 #19052

Compilation message

Subtask #1 10.0 / 10.0

Subtask #2 27.0 / 27.0

Subtask #3 26.0 / 26.0

Subtask #4 0.0 / 17.0

Subtask #5 0.0 / 20.0

Subtask #1
10.0 / 10.0

Subtask #2
27.0 / 27.0

Subtask #3
26.0 / 26.0

Subtask #4
0.0 / 17.0

Subtask #5
0.0 / 20.0