oj.uz

Submission #16832

# Submission time Handle Problem Language Result Execution time Memory
16832 2015-10-07T05:05:00 Z comet Game (IOI13_game) C++
100 / 100
 7724 ms 99716 KB 
#include <bits/stdc++.h>
#include "game.h"
using namespace std;
typedef long long ll;
ll gcd2(ll,ll);
int R,C;
struct Node{
    int s,e;
    ll GCD;
    Node *LL,*RR,*p;
    Node(int s_,int e_):s(s_),e(e_){
        GCD=0;
        LL=RR=p=NULL;
    }
    ~Node(){
        if(LL!=NULL)delete LL;
        if(RR!=NULL)delete RR;
    }
    void up(){
        ll z0=0,z1=0;
        if(LL!=NULL)z0=LL->GCD;
        if(RR!=NULL)z1=RR->GCD;
        GCD=gcd2(z0,z1);
    }
    void update(int x,ll c){
        int mid=(s+e)/2;
        if(x<s||x>e){
            int pL=p->s,pR=p->e,L,R;
            L=pL,R=pR;
            while(L<=s&&e<=R){
                pL=L,pR=R;
                mid=(L+R)/2;
                if(x<=mid)R=mid;
                else L=mid+1;
            }
            Node* t=new Node(pL,pR);
            mid=(p->s+p->e)/2;
            if(pR<=mid)p->LL=t;
            else p->RR=t;
            mid=(pL+pR)/2;
            if(x<=mid)t->RR=this;
            else t->LL=this;
            t->p=p;
            p=t;
            t->update(x,c);
            return;
        }
        if(s==e){
            GCD=c;
            return;
        }
        if(x<=mid){
            if(LL==NULL){
                LL=new Node(x,x);
                LL->p=this;
            }
            LL->update(x,c);
        }
        else{
            if(RR==NULL){
                RR=new Node(x,x);
                RR->p=this;
            }
            RR->update(x,c);
        }
        up();
    }
    ll query(int L,int R){
        if(e<L||s>R)return 0;
        if(L<=s&&e<=R)return GCD;
        ll z0=0,z1=0;
        if(LL!=NULL)z0=LL->query(L,R);
        if(RR!=NULL)z1=RR->query(L,R);
        return gcd2(z0,z1);
    }
};

struct SegTree{
    Node *root;
    SegTree(int s=0,int e=0){
        root=new Node(s,e);
    }
    void finish(){
        delete root;
    }
    void update(int x,ll c){
        root->update(x,c);
    }
    ll query(int s,int e){
        return root->query(s,e);
    }
};

struct Node2{
    int s,e;
    SegTree tree;
    Node2 *LL,*RR;
    Node2(int s_,int e_):s(s_),e(e_){
        tree=SegTree(0,R-1);
        LL=RR=NULL;
    }
    ~Node2(){
        if(LL!=NULL)delete LL;
        if(RR!=NULL)delete RR;
    }
    void update(int x,int y,ll c){
        int mid=(s+e)/2;
        if(s==e){
            tree.update(y,c);
            return;
        }
        if(x<=mid){
            if(LL==NULL)LL=new Node2(s,mid);
            LL->update(x,y,c);
        }
        else{
            if(RR==NULL)RR=new Node2(mid+1,e);
            RR->update(x,y,c);
        }
        ll z0=0,z1=0;
        if(LL!=NULL)z0=LL->tree.query(y,y);
        if(RR!=NULL)z1=RR->tree.query(y,y);
        tree.update(y,gcd2(z0,z1));
    }
    ll query(int lo,int hi,int L,int R){
        if(e<lo||s>hi)return 0;
        if(lo<=s&&e<=hi)return tree.query(L,R);
        ll z0=0,z1=0;
        if(LL!=NULL)z0=LL->query(lo,hi,L,R);
        if(RR!=NULL)z1=RR->query(lo,hi,L,R);
        return gcd2(z0,z1);
    }
};

struct SegTree2{
    Node2 *root;
    SegTree2(int s=0,int e=0){
        root=new Node2(s,e);
    }
    void finish(){
        delete root;
    }
    void update(int x,int y,ll c){
        root->update(x,y,c);
    }
    ll query(int lo,int hi,int L,int R){
        return root->query(lo,hi,L,R);
    }
}game;

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

void init(int R_, int C_) {
    R=R_,C=C_;
    game=SegTree2(0,C-1);
}

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

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

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 1772 KB Output is correct
2 Correct 0 ms 1772 KB Output is correct
3 Correct 0 ms 1772 KB Output is correct
4 Correct 0 ms 1772 KB Output is correct
5 Correct 0 ms 1772 KB Output is correct
6 Correct 0 ms 1772 KB Output is correct
7 Correct 0 ms 1772 KB Output is correct
8 Correct 0 ms 1772 KB Output is correct
9 Correct 0 ms 1772 KB Output is correct
10 Correct 1 ms 1772 KB Output is correct
11 Correct 0 ms 1772 KB Output is correct
12 Correct 0 ms 1772 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 1772 KB Output is correct
2 Correct 0 ms 1772 KB Output is correct
3 Correct 0 ms 1772 KB Output is correct
4 Correct 786 ms 12464 KB Output is correct
5 Correct 682 ms 12596 KB Output is correct
6 Correct 1109 ms 12860 KB Output is correct
7 Correct 1254 ms 12860 KB Output is correct
8 Correct 740 ms 7976 KB Output is correct
9 Correct 1205 ms 12860 KB Output is correct
10 Correct 1063 ms 12860 KB Output is correct
11 Correct 0 ms 1772 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 1772 KB Output is correct
2 Correct 0 ms 1772 KB Output is correct
3 Correct 0 ms 1772 KB Output is correct
4 Correct 0 ms 1772 KB Output is correct
5 Correct 0 ms 1772 KB Output is correct
6 Correct 0 ms 1772 KB Output is correct
7 Correct 0 ms 1772 KB Output is correct
8 Correct 0 ms 1772 KB Output is correct
9 Correct 0 ms 1772 KB Output is correct
10 Correct 0 ms 1772 KB Output is correct
11 Correct 0 ms 1772 KB Output is correct
12 Correct 1283 ms 9032 KB Output is correct
13 Correct 2953 ms 5732 KB Output is correct
14 Correct 355 ms 1772 KB Output is correct
15 Correct 3537 ms 7052 KB Output is correct
16 Correct 281 ms 10880 KB Output is correct
17 Correct 1298 ms 6656 KB Output is correct
18 Correct 2190 ms 10880 KB Output is correct
19 Correct 1857 ms 10880 KB Output is correct
20 Correct 1722 ms 10880 KB Output is correct
21 Correct 0 ms 1772 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 1772 KB Output is correct
2 Correct 0 ms 1772 KB Output is correct
3 Correct 0 ms 1772 KB Output is correct
4 Correct 0 ms 1772 KB Output is correct
5 Correct 0 ms 1772 KB Output is correct
6 Correct 0 ms 1772 KB Output is correct
7 Correct 0 ms 1772 KB Output is correct
8 Correct 0 ms 1772 KB Output is correct
9 Correct 1 ms 1772 KB Output is correct
10 Correct 0 ms 1772 KB Output is correct
11 Correct 0 ms 1772 KB Output is correct
12 Correct 789 ms 12464 KB Output is correct
13 Correct 666 ms 12596 KB Output is correct
14 Correct 1089 ms 12860 KB Output is correct
15 Correct 1239 ms 12860 KB Output is correct
16 Correct 738 ms 7976 KB Output is correct
17 Correct 1203 ms 12860 KB Output is correct
18 Correct 1105 ms 12860 KB Output is correct
19 Correct 1283 ms 9032 KB Output is correct
20 Correct 3045 ms 5732 KB Output is correct
21 Correct 333 ms 1772 KB Output is correct
22 Correct 3636 ms 7052 KB Output is correct
23 Correct 301 ms 10880 KB Output is correct
24 Correct 1340 ms 6656 KB Output is correct
25 Correct 2209 ms 10880 KB Output is correct
26 Correct 1965 ms 10880 KB Output is correct
27 Correct 1772 ms 10880 KB Output is correct
28 Correct 746 ms 47312 KB Output is correct
29 Correct 2255 ms 46916 KB Output is correct
30 Correct 5536 ms 36752 KB Output is correct
31 Correct 4917 ms 28172 KB Output is correct
32 Correct 495 ms 1904 KB Output is correct
33 Correct 762 ms 2696 KB Output is correct
34 Correct 420 ms 46916 KB Output is correct
35 Correct 1728 ms 24476 KB Output is correct
36 Correct 3128 ms 46916 KB Output is correct
37 Correct 2561 ms 46916 KB Output is correct
38 Correct 2500 ms 46916 KB Output is correct
39 Correct 2225 ms 36356 KB Output is correct
40 Correct 0 ms 1772 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 1772 KB Output is correct
2 Correct 0 ms 1772 KB Output is correct
3 Correct 1 ms 1772 KB Output is correct
4 Correct 0 ms 1772 KB Output is correct
5 Correct 0 ms 1772 KB Output is correct
6 Correct 0 ms 1772 KB Output is correct
7 Correct 0 ms 1772 KB Output is correct
8 Correct 0 ms 1772 KB Output is correct
9 Correct 0 ms 1772 KB Output is correct
10 Correct 0 ms 1772 KB Output is correct
11 Correct 0 ms 1772 KB Output is correct
12 Correct 784 ms 12464 KB Output is correct
13 Correct 672 ms 12596 KB Output is correct
14 Correct 1124 ms 12860 KB Output is correct
15 Correct 1300 ms 12860 KB Output is correct
16 Correct 706 ms 7976 KB Output is correct
17 Correct 1247 ms 12860 KB Output is correct
18 Correct 1130 ms 12860 KB Output is correct
19 Correct 1328 ms 9032 KB Output is correct
20 Correct 3068 ms 5732 KB Output is correct
21 Correct 352 ms 1772 KB Output is correct
22 Correct 3654 ms 7052 KB Output is correct
23 Correct 333 ms 10880 KB Output is correct
24 Correct 1301 ms 6656 KB Output is correct
25 Correct 2246 ms 10880 KB Output is correct
26 Correct 1935 ms 10880 KB Output is correct
27 Correct 1766 ms 10880 KB Output is correct
28 Correct 720 ms 47312 KB Output is correct
29 Correct 2278 ms 46916 KB Output is correct
30 Correct 5509 ms 36752 KB Output is correct
31 Correct 4892 ms 28172 KB Output is correct
32 Correct 403 ms 1904 KB Output is correct
33 Correct 771 ms 2696 KB Output is correct
34 Correct 398 ms 46916 KB Output is correct
35 Correct 1699 ms 24476 KB Output is correct
36 Correct 3097 ms 46916 KB Output is correct
37 Correct 2542 ms 46916 KB Output is correct
38 Correct 2477 ms 46916 KB Output is correct
39 Correct 944 ms 99716 KB Output is correct
40 Correct 3615 ms 98660 KB Output is correct
41 Correct 7724 ms 76484 KB Output is correct
42 Correct 6897 ms 58004 KB Output is correct
43 Correct 761 ms 98792 KB Output is correct
44 Correct 619 ms 2036 KB Output is correct
45 Correct 2169 ms 36356 KB Output is correct
46 Correct 4022 ms 98792 KB Output is correct
47 Correct 3974 ms 98792 KB Output is correct
48 Correct 3743 ms 98660 KB Output is correct
49 Correct 0 ms 1772 KB Output is correct