oj.uz

Submission #372847

# Submission time Handle Problem Language Result Execution time Memory
372847 2021-03-02T01:58:52 Z errorgorn Game (IOI13_game) C++17
100 / 100
 3230 ms 38092 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

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

Subtask #1
10.0 / 10.0

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

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB Output is correct
2 Correct 0 ms 256 KB Output is correct
3 Correct 1 ms 256 KB Output is correct
4 Correct 485 ms 9604 KB Output is correct
5 Correct 350 ms 9996 KB Output is correct
6 Correct 464 ms 6644 KB Output is correct
7 Correct 552 ms 6380 KB Output is correct
8 Correct 331 ms 4460 KB Output is correct
9 Correct 510 ms 6380 KB Output is correct
10 Correct 480 ms 5996 KB Output is correct
11 Correct 0 ms 256 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 0 ms 256 KB Output is correct
5 Correct 0 ms 256 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 0 ms 256 KB Output is correct
8 Correct 0 ms 256 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Correct 719 ms 11884 KB Output is correct
13 Correct 1201 ms 5412 KB Output is correct
14 Correct 236 ms 1004 KB Output is correct
15 Correct 1317 ms 6336 KB Output is correct
16 Correct 290 ms 10860 KB Output is correct
17 Correct 738 ms 6920 KB Output is correct
18 Correct 1555 ms 11096 KB Output is correct
19 Correct 1274 ms 11116 KB Output is correct
20 Correct 1143 ms 10524 KB Output is correct
21 Correct 1 ms 256 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 0 ms 256 KB Output is correct
5 Correct 0 ms 256 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 256 KB Output is correct
8 Correct 0 ms 256 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Correct 464 ms 9580 KB Output is correct
13 Correct 350 ms 10044 KB Output is correct
14 Correct 477 ms 6484 KB Output is correct
15 Correct 563 ms 6288 KB Output is correct
16 Correct 342 ms 4588 KB Output is correct
17 Correct 523 ms 6380 KB Output is correct
18 Correct 523 ms 5996 KB Output is correct
19 Correct 755 ms 12012 KB Output is correct
20 Correct 1172 ms 5108 KB Output is correct
21 Correct 251 ms 1004 KB Output is correct
22 Correct 1311 ms 6372 KB Output is correct
23 Correct 270 ms 10604 KB Output is correct
24 Correct 715 ms 6892 KB Output is correct
25 Correct 1535 ms 11064 KB Output is correct
26 Correct 1234 ms 11224 KB Output is correct
27 Correct 1239 ms 10604 KB Output is correct
28 Correct 506 ms 16236 KB Output is correct
29 Correct 1249 ms 19088 KB Output is correct
30 Correct 2248 ms 13280 KB Output is correct
31 Correct 2106 ms 10168 KB Output is correct
32 Correct 260 ms 1004 KB Output is correct
33 Correct 383 ms 1152 KB Output is correct
34 Correct 764 ms 16108 KB Output is correct
35 Correct 888 ms 8428 KB Output is correct
36 Correct 1880 ms 16216 KB Output is correct
37 Correct 1439 ms 16620 KB Output is correct
38 Correct 1393 ms 15852 KB Output is correct
39 Correct 1160 ms 12576 KB Output is correct
40 Correct 1 ms 256 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 256 KB Output is correct
5 Correct 0 ms 256 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 256 KB Output is correct
8 Correct 1 ms 256 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Correct 474 ms 9580 KB Output is correct
13 Correct 342 ms 9992 KB Output is correct
14 Correct 474 ms 6508 KB Output is correct
15 Correct 555 ms 6380 KB Output is correct
16 Correct 332 ms 4572 KB Output is correct
17 Correct 632 ms 6508 KB Output is correct
18 Correct 516 ms 6044 KB Output is correct
19 Correct 719 ms 12012 KB Output is correct
20 Correct 1150 ms 5356 KB Output is correct
21 Correct 238 ms 1132 KB Output is correct
22 Correct 1329 ms 6396 KB Output is correct
23 Correct 268 ms 10604 KB Output is correct
24 Correct 727 ms 6840 KB Output is correct
25 Correct 1551 ms 10988 KB Output is correct
26 Correct 1209 ms 11188 KB Output is correct
27 Correct 1172 ms 10720 KB Output is correct
28 Correct 496 ms 15980 KB Output is correct
29 Correct 1283 ms 19052 KB Output is correct
30 Correct 2228 ms 13164 KB Output is correct
31 Correct 2173 ms 10348 KB Output is correct
32 Correct 270 ms 1108 KB Output is correct
33 Correct 388 ms 1392 KB Output is correct
34 Correct 780 ms 15936 KB Output is correct
35 Correct 814 ms 8556 KB Output is correct
36 Correct 1940 ms 16380 KB Output is correct
37 Correct 1437 ms 16496 KB Output is correct
38 Correct 1441 ms 15948 KB Output is correct
39 Correct 654 ms 36556 KB Output is correct
40 Correct 2231 ms 38092 KB Output is correct
41 Correct 3230 ms 30224 KB Output is correct
42 Correct 2818 ms 22116 KB Output is correct
43 Correct 1018 ms 36076 KB Output is correct
44 Correct 306 ms 1164 KB Output is correct
45 Correct 1165 ms 12792 KB Output is correct
46 Correct 2631 ms 36460 KB Output is correct
47 Correct 2493 ms 36376 KB Output is correct
48 Correct 2485 ms 35972 KB Output is correct
49 Correct 1 ms 256 KB Output is correct