oj.uz

Submission #372846

# Submission time Handle Problem Language Result Execution time Memory
372846 2021-03-02T01:56:19 Z errorgorn Game (IOI13_game) C++17
100 / 100
 2801 ms 48620 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 l,int r,int pos){ //find lca of 2 nodes
	if (pos<l){
		int p=32-__builtin_clz(pos^l);
		int lp=(pos>>p)<<p;
		return ii(lp,lp+(1<<p)-1);
	}
	if (r<pos){
		int p=32-__builtin_clz(r^pos);
		int lp=(l>>p)<<p;
		return ii(lp,lp+(1<<p)-1);
	}
}
 
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(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(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,(1<<30)-1);
    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(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(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,(1<<30)-1);
 
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 constructor 'node::node(int, int)':
game.cpp:36:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   36 |         s=_s,e=_e,m=s+e>>1;
      |                     ~^~
game.cpp: In constructor 'node2d::node2d(int, int)':
game.cpp:94:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   94 |         s=_s,e=_e,m=s+e>>1;
      |                     ~^~
game.cpp: In function 'ii lca(int, int, int)':
game.cpp:28:1: warning: control reaches end of non-void function [-Wreturn-type]
   28 | }
      | ^

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 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 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 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 1 ms 364 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 502 ms 14060 KB Output is correct
5 Correct 334 ms 13804 KB Output is correct
6 Correct 478 ms 11244 KB Output is correct
7 Correct 548 ms 11244 KB Output is correct
8 Correct 330 ms 8812 KB Output is correct
9 Correct 525 ms 11116 KB Output is correct
10 Correct 493 ms 10680 KB Output is correct
11 Correct 1 ms 364 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 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 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 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 911 ms 16172 KB Output is correct
13 Correct 1430 ms 9320 KB Output is correct
14 Correct 243 ms 5612 KB Output is correct
15 Correct 1539 ms 10836 KB Output is correct
16 Correct 330 ms 14848 KB Output is correct
17 Correct 700 ms 11756 KB Output is correct
18 Correct 1513 ms 16256 KB Output is correct
19 Correct 1190 ms 16364 KB Output is correct
20 Correct 1085 ms 15724 KB Output is correct
21 Correct 1 ms 364 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 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 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 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 463 ms 14060 KB Output is correct
13 Correct 345 ms 14016 KB Output is correct
14 Correct 453 ms 11116 KB Output is correct
15 Correct 536 ms 10860 KB Output is correct
16 Correct 332 ms 8808 KB Output is correct
17 Correct 587 ms 10988 KB Output is correct
18 Correct 529 ms 10732 KB Output is correct
19 Correct 874 ms 15968 KB Output is correct
20 Correct 1419 ms 9444 KB Output is correct
21 Correct 242 ms 5740 KB Output is correct
22 Correct 1560 ms 11116 KB Output is correct
23 Correct 337 ms 14828 KB Output is correct
24 Correct 706 ms 11500 KB Output is correct
25 Correct 1428 ms 16128 KB Output is correct
26 Correct 1153 ms 16492 KB Output is correct
27 Correct 1113 ms 15724 KB Output is correct
28 Correct 492 ms 26732 KB Output is correct
29 Correct 1168 ms 29000 KB Output is correct
30 Correct 2001 ms 19540 KB Output is correct
31 Correct 1836 ms 16796 KB Output is correct
32 Correct 262 ms 10296 KB Output is correct
33 Correct 365 ms 10220 KB Output is correct
34 Correct 538 ms 22688 KB Output is correct
35 Correct 809 ms 18540 KB Output is correct
36 Correct 1870 ms 27048 KB Output is correct
37 Correct 1373 ms 27132 KB Output is correct
38 Correct 1383 ms 26476 KB Output is correct
39 Correct 1112 ms 23484 KB Output is correct
40 Correct 0 ms 364 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 364 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 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 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 469 ms 14060 KB Output is correct
13 Correct 332 ms 13804 KB Output is correct
14 Correct 457 ms 11244 KB Output is correct
15 Correct 547 ms 11040 KB Output is correct
16 Correct 352 ms 8684 KB Output is correct
17 Correct 517 ms 10944 KB Output is correct
18 Correct 514 ms 10604 KB Output is correct
19 Correct 902 ms 16108 KB Output is correct
20 Correct 1419 ms 9636 KB Output is correct
21 Correct 241 ms 5740 KB Output is correct
22 Correct 1558 ms 10876 KB Output is correct
23 Correct 350 ms 14700 KB Output is correct
24 Correct 699 ms 11628 KB Output is correct
25 Correct 1509 ms 16408 KB Output is correct
26 Correct 1166 ms 16492 KB Output is correct
27 Correct 1129 ms 15940 KB Output is correct
28 Correct 464 ms 26872 KB Output is correct
29 Correct 1171 ms 29164 KB Output is correct
30 Correct 1958 ms 19904 KB Output is correct
31 Correct 1883 ms 16636 KB Output is correct
32 Correct 261 ms 10220 KB Output is correct
33 Correct 364 ms 10220 KB Output is correct
34 Correct 525 ms 22764 KB Output is correct
35 Correct 783 ms 18284 KB Output is correct
36 Correct 1894 ms 26960 KB Output is correct
37 Correct 1370 ms 26992 KB Output is correct
38 Correct 1355 ms 26532 KB Output is correct
39 Correct 648 ms 47212 KB Output is correct
40 Correct 2007 ms 48620 KB Output is correct
41 Correct 2801 ms 35500 KB Output is correct
42 Correct 2471 ms 27884 KB Output is correct
43 Correct 795 ms 43372 KB Output is correct
44 Correct 305 ms 10880 KB Output is correct
45 Correct 1067 ms 22892 KB Output is correct
46 Correct 2455 ms 47524 KB Output is correct
47 Correct 2431 ms 47332 KB Output is correct
48 Correct 2362 ms 47180 KB Output is correct
49 Correct 0 ms 364 KB Output is correct