Submission #372847

#	Time	Username	Problem	Language	Result	Execution time	Memory
372847		errorgorn	Game (IOI13_game)	C++17	100 / 100	3230 ms	38092 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 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 (stderr)

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