Submission #372846

#	Time	Username	Problem	Language	Result	Execution time	Memory
372846		errorgorn	Game (IOI13_game)	C++17	100 / 100	2801 ms	48620 KiB

game

#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 (stderr)

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 / 10
• Subtask 2: 27 / 27
• Subtask 3: 26 / 26
• Subtask 4: 17 / 17
• Subtask 5: 20 / 20