oj.uz

Submission #19052

# Submission time Handle Problem Language Result Execution time Memory
19052 2016-02-17T11:42:54 Z tlwpdus Game (IOI13_game) C++
63 / 100
 3327 ms 256000 KB 
#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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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 -