oj.uz

Submission #173425

# Submission time Handle Problem Language Result Execution time Memory
173425 2020-01-04T05:20:57 Z errorgorn Game (IOI13_game) C++14
100 / 100
 5236 ms 48516 KB 
#include "game.h"
#include <cstdio>
#include <utility>
using namespace std;
typedef pair<int,int> ii;

inline long long func(long long X, long long Y) {
    long long tmp;
    while (X != Y && Y != 0) {
        tmp = X;
        X = Y;
        Y = tmp % Y;
    }
    return X;
}

ii lca(int s,int e,int l,int r,int pos){
    int m=s+e>>1;
    if (r<=m && m<pos) return ii(s,e);
    else if (pos<=m && m<l) return ii(s,e);
    if (pos<=m) return lca(s,m,l,r,pos);
    else return lca(m+1,e,l,r,pos);
}

struct node{
    int s,e,m;
    long long val=0;
    node *l=nullptr,*r=nullptr;

    node (int _s,int _e){
        s=_s,e=_e,m=s+e>>1;
    }

    bool inside(int i){
        return s<=i && i<=e;
    }

    void update(int i,long long j){
        if (s==e) val=j;
        else{
            if (i<=m){
                if (l==nullptr) l=new node(i,i);
                else if (!l->inside(i)){
                    node *temp=l;
                    ii child=lca(s,e,l->s,l->e,i);
                    l=new node(child.first,child.second);
                    if (temp->e<=l->m) l->l=temp;
                    else l->r=temp;
                }
                l->update(i,j);
            }
            else{
                if (r==nullptr) r=new node(i,i);
                else if (!r->inside(i)){
                    node *temp=r;
                    ii child=lca(s,e,r->s,r->e,i);
                    r=new node(child.first,child.second);
                    if (temp->e<=r->m) r->l=temp;
                    else r->r=temp;
                }
                r->update(i,j);
            }
            val=func((l==nullptr)?0:l->val,(r==nullptr)?0:r->val);
        }
    }

    long long query(int i,int j){
        if (i<=s && e<=j) return val;
        else if (j<=m) return (l==nullptr)?0:l->query(i,j);
        else if (m<i) return (r==nullptr)?0:r->query(i,j);
        else return func((l==nullptr)?0:l->query(i,m),(r==nullptr)?0:r->query(m+1,j));
    }

    node* clone(){
        node* res=new node(s,e);
        res->val=val;
        res->l=(l==nullptr)?nullptr:l->clone();
        res->r=(r==nullptr)?nullptr:r->clone();
        return res;
    }
};

struct node2d{
    int s,e,m;
    node *val=new node(0,1000000000);
    node2d *l=nullptr,*r=nullptr;

    node2d (int _s,int _e){
        s=_s,e=_e,m=s+e>>1;
    }

    bool inside(int i){
        return s<=i && i<=e;
    }

    void update(int i,int j,long long k){
        if (s==e) val->update(j,k);
        else{
            if (i<=m){
                if (l==nullptr) l=new node2d(i,i);
                else if (!l->inside(i)){
                    node2d *temp=l;
                    ii child=lca(s,e,l->s,l->e,i);
                    l=new node2d(child.first,child.second);
                    if (temp->e<=l->m) l->l=temp;
                    else l->r=temp;
                    l->val=temp->val->clone();
                }
                l->update(i,j,k);
            }
            else{
                if (r==nullptr) r=new node2d(i,i);
                else if (!r->inside(i)){
                    node2d *temp=r;
                    ii child=lca(s,e,r->s,r->e,i);
                    r=new node2d(child.first,child.second);
                    if (temp->e<=r->m) r->l=temp;
                    else r->r=temp;
                    r->val=temp->val->clone();
                }
                r->update(i,j,k);
            }
            val->update(j,func((l==nullptr)?0:l->val->query(j,j),(r==nullptr)?0:r->val->query(j,j)));
        }
    }

    long long query(int i,int j,int i2,int j2){
        if (i<=s && e<=j) return val->query(i2,j2);
        else if (j<=m) return (l==nullptr)?0:l->query(i,j,i2,j2);
        else if (m<i) return (r==nullptr)?0:r->query(i,j,i2,j2);
        else return func((l==nullptr)?0:l->query(i,m,i2,j2),(r==nullptr)?0:r->query(m+1,j,i2,j2));
    }
}*root=new node2d(0,1000000000);

void init(int R, int C) {
}

void update(int P, int Q, long long K) {
   root->update(P,Q,K);
}

long long calculate(int P, int Q, int U, int V) {
    return root->query(P,U,Q,V);
}

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 'ii lca(int, int, int, int, int)':
game.cpp:18:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int m=s+e>>1;
           ~^~
game.cpp: In constructor 'node::node(int, int)':
game.cpp:31:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
         s=_s,e=_e,m=s+e>>1;
                     ~^~
game.cpp: In constructor 'node2d::node2d(int, int)':
game.cpp:89:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
         s=_s,e=_e,m=s+e>>1;
                     ~^~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 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 376 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 380 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 256 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 576 ms 14096 KB Output is correct
5 Correct 368 ms 13816 KB Output is correct
6 Correct 654 ms 11380 KB Output is correct
7 Correct 775 ms 11000 KB Output is correct
8 Correct 464 ms 8696 KB Output is correct
9 Correct 718 ms 11108 KB Output is correct
10 Correct 587 ms 10748 KB Output is correct
11 Correct 2 ms 256 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 3 ms 376 KB Output is correct
3 Correct 2 ms 376 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 376 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 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 905 ms 16084 KB Output is correct
13 Correct 1926 ms 9228 KB Output is correct
14 Correct 276 ms 5756 KB Output is correct
15 Correct 2211 ms 10928 KB Output is correct
16 Correct 296 ms 14840 KB Output is correct
17 Correct 1083 ms 11744 KB Output is correct
18 Correct 1896 ms 16376 KB Output is correct
19 Correct 1582 ms 16496 KB Output is correct
20 Correct 1490 ms 16072 KB Output is correct
21 Correct 2 ms 376 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 3 ms 376 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 256 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 256 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 256 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 565 ms 14072 KB Output is correct
13 Correct 371 ms 13868 KB Output is correct
14 Correct 646 ms 11260 KB Output is correct
15 Correct 735 ms 10872 KB Output is correct
16 Correct 457 ms 8860 KB Output is correct
17 Correct 707 ms 11088 KB Output is correct
18 Correct 588 ms 10800 KB Output is correct
19 Correct 850 ms 16140 KB Output is correct
20 Correct 1915 ms 9176 KB Output is correct
21 Correct 274 ms 5672 KB Output is correct
22 Correct 2189 ms 10788 KB Output is correct
23 Correct 300 ms 14796 KB Output is correct
24 Correct 1121 ms 11720 KB Output is correct
25 Correct 1871 ms 16296 KB Output is correct
26 Correct 1633 ms 16496 KB Output is correct
27 Correct 1405 ms 16056 KB Output is correct
28 Correct 559 ms 26616 KB Output is correct
29 Correct 1536 ms 28960 KB Output is correct
30 Correct 3869 ms 20380 KB Output is correct
31 Correct 3555 ms 17216 KB Output is correct
32 Correct 328 ms 10124 KB Output is correct
33 Correct 508 ms 10488 KB Output is correct
34 Correct 1126 ms 22736 KB Output is correct
35 Correct 1193 ms 18276 KB Output is correct
36 Correct 2336 ms 26996 KB Output is correct
37 Correct 1906 ms 27056 KB Output is correct
38 Correct 1763 ms 26540 KB Output is correct
39 Correct 1547 ms 23004 KB Output is correct
40 Correct 2 ms 256 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 3 ms 376 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 2 ms 256 KB Output is correct
6 Correct 2 ms 380 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 252 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 558 ms 14052 KB Output is correct
13 Correct 396 ms 14008 KB Output is correct
14 Correct 653 ms 11184 KB Output is correct
15 Correct 721 ms 11080 KB Output is correct
16 Correct 450 ms 8884 KB Output is correct
17 Correct 753 ms 11232 KB Output is correct
18 Correct 589 ms 10696 KB Output is correct
19 Correct 849 ms 15984 KB Output is correct
20 Correct 1961 ms 9312 KB Output is correct
21 Correct 278 ms 5752 KB Output is correct
22 Correct 2230 ms 10836 KB Output is correct
23 Correct 304 ms 14968 KB Output is correct
24 Correct 1108 ms 11980 KB Output is correct
25 Correct 2065 ms 16432 KB Output is correct
26 Correct 1634 ms 16616 KB Output is correct
27 Correct 1399 ms 15988 KB Output is correct
28 Correct 587 ms 26620 KB Output is correct
29 Correct 1699 ms 28872 KB Output is correct
30 Correct 3878 ms 20344 KB Output is correct
31 Correct 3569 ms 17232 KB Output is correct
32 Correct 331 ms 10160 KB Output is correct
33 Correct 495 ms 10220 KB Output is correct
34 Correct 1112 ms 22908 KB Output is correct
35 Correct 1274 ms 18464 KB Output is correct
36 Correct 2288 ms 26956 KB Output is correct
37 Correct 1837 ms 27200 KB Output is correct
38 Correct 1744 ms 26316 KB Output is correct
39 Correct 749 ms 47312 KB Output is correct
40 Correct 2483 ms 48516 KB Output is correct
41 Correct 5236 ms 37520 KB Output is correct
42 Correct 4868 ms 29436 KB Output is correct
43 Correct 1462 ms 43332 KB Output is correct
44 Correct 390 ms 10616 KB Output is correct
45 Correct 1587 ms 22904 KB Output is correct
46 Correct 3302 ms 47328 KB Output is correct
47 Correct 3324 ms 47456 KB Output is correct
48 Correct 3022 ms 46740 KB Output is correct
49 Correct 2 ms 256 KB Output is correct