Submission #1167107

#	Time	Username	Problem	Language	Result	Execution time	Memory
1167107		8pete8	Game (IOI13_game)	C++20	100 / 100	9240 ms	54228 KiB

game

#include "game.h"
#include<iostream>
#include<stack>
#include<map>
#include<vector>
#include<string>
#include<cassert>
#include<unordered_map>
#include <queue>
#include <cstdint>
#include<cstring>
#include<limits.h>
#include<cmath>
#include<set>
#include<algorithm>
#include <iomanip>
#include<numeric>
#include<bitset>
#include <chrono>
#include<random>
using namespace std;
#define ll long long
#define f first
#define s second
#define pii pair<int,int>
#define ppii pair<int,pii>
#define vi vector<int>
#define pb push_back
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define F(n) for(int i=0;i<n;i++)
#define lb lower_bound
#define ub upper_bound
#define fastio ios::sync_with_stdio(false);cin.tie(NULL);
#pragma GCC optimize ("03,unroll-lopps")
#define sz(x) (int)((x).size())
#define int long long
const int mxn=3e5,inf=1e18,Mxn=1e7;
long long gcd2(long long X, long long Y) {
    long long tmp;
    while (X != Y && Y != 0){
        tmp = X;
        X = Y;
        Y = tmp % Y;
    }
    return X;
}
mt19937_64 rng(5);

struct node{
    node *l,*r;
    int col,row,val,G,p;
    node(int x,int y,int z):l(0),r(0),p(rng()),row(x),col(y),val(z),G(z){};
};
struct treap{
    node *root=0;
    int get(node *&a){
        if(a==NULL)return 0;
        return a->G;
    }
    void pull(node *&x){
        if(x==NULL)return;
        x->G=gcd(x->val,gcd(get(x->l),get(x->r)));
    }
    void split(node *&L,node *&R,node *cur,int row,int col){
        if(cur==NULL)return void(L=R=NULL);
        if(cur->col<col||(cur->col==col&&cur->row<=row)){
            split(cur->r,R,cur->r,row,col);
            L=cur;
        }
        else{
            split(L,cur->l,cur->l,row,col);
            R=cur;
        }
        pull(L);
        pull(R);
    }
    void merge(node *a,node *b,node *&cur){
        if(a==NULL)return void(cur=b);
        if(b==NULL)return void(cur=a);
        if(a->p<=b->p)merge(a->r,b,a->r),cur=a;
        else merge(a,b->l,b->l),cur=b;
        pull(cur);
    }
    bool change(node *&cur,int x,int y,int z){
        if(cur==NULL)return 0;
        if(cur->r!=NULL){
            if(change(cur->r,x,y,z)){
                pull(cur);
                return 1;
            }
            return 0;
        }
        else if(cur->row==x&&cur->col==y){
            cur->val=cur->G=z;
            pull(cur);
            return 1;
        }
        pull(cur);
        return 0;
    }
};
treap row[4*mxn+10];
int L[Mxn+10],R[Mxn+10],T=1;
void init(int32_t R, int32_t C){
    return;
}
void upd(int id,int32_t P, int32_t Q, long long K){
    node *x=new node(P,Q,K);
    if(row[id].root==NULL)row[id].root=x;
    else{
        node *R=NULL;
        row[id].split(row[id].root,R,row[id].root,P,Q);
        if(row[id].change(row[id].root,P,Q,K))return void(row[id].merge(row[id].root,R,row[id].root));
        row[id].merge(row[id].root,x,row[id].root);
        row[id].merge(row[id].root,R,row[id].root);
    }
}
int get(int x,int U,int V){
    node *L=NULL,*R=NULL;
    if(row[x].root==NULL)return 0;
    row[x].split(L,row[x].root,row[x].root,inf,U-1);
    row[x].split(row[x].root,R,row[x].root,inf,V);
    int ans=(row[x].root==NULL)?0:row[x].root->G;
    row[x].merge(L,row[x].root,row[x].root);
    row[x].merge(row[x].root,R,row[x].root);
    return ans;
}
void updateseg(int qx,int qy,int x,int pos,int l,int r){
    if(l>qx||r<qx)return;
    if(l<=qx&&qx<=r){

        upd(pos,qx,qy,x);
    }
    if(l==r)return;
    int mid=l+(r-l)/2;
    if(qx<=mid){
        if(!L[pos])L[pos]=++T;
        updateseg(qx,qy,x,L[pos],l,mid);
    }
    else{
        if(!R[pos])R[pos]=++T;
        updateseg(qx,qy,x,R[pos],mid+1,r);
    }
}
int qryseg(int qlx,int qrx,int qly,int qry,int pos,int l,int r){
    if(pos==0)return 0;
    if(l>qrx||r<qlx)return 0;
    if(qlx<=l&&r<=qrx){
        return get(pos,qly,qry);
    }
    int mid=l+(r-l)/2;
    return gcd(qryseg(qlx,qrx,qly,qry,L[pos],l,mid),qryseg(qlx,qrx,qly,qry,R[pos],mid+1,r));
}
void update(int32_t P,int32_t Q,int x){
    updateseg(P,Q,x,1,0,1e9);
}
//col U->V
long long calculate(int32_t P, int32_t Q, int32_t U, int32_t V){
    int ans=0;
    return qryseg(P,U,Q,V,1,0,1e9);
    return ans;
}

Compilation message (stderr)

game.cpp:35:40: warning: bad option '-funroll-lopps' to pragma 'optimize' [-Wpragmas]
   35 | #pragma GCC optimize ("03,unroll-lopps")
      |                                        ^
game.cpp:39:40: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   39 | long long gcd2(long long X, long long Y) {
      |                                        ^
game.cpp:53:27: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   53 |     node(int x,int y,int z):l(0),r(0),p(rng()),row(x),col(y),val(z),G(z){};
      |                           ^
game.cpp:57:21: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   57 |     int get(node *&a){
      |                     ^
game.cpp:61:23: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   61 |     void pull(node *&x){
      |                       ^
game.cpp:65:59: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   65 |     void split(node *&L,node *&R,node *cur,int row,int col){
      |                                                           ^
game.cpp:78:42: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   78 |     void merge(node *a,node *b,node *&cur){
      |                                          ^
game.cpp:85:45: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   85 |     bool change(node *&cur,int x,int y,int z){
      |                                             ^
game.cpp:105:31: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
  105 | void init(int32_t R, int32_t C){
      |                               ^
game.cpp:108:50: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
  108 | void upd(int id,int32_t P, int32_t Q, long long K){
      |                                                  ^
game.cpp:119:26: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
  119 | int get(int x,int U,int V){
      |                          ^
game.cpp:129:55: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
  129 | void updateseg(int qx,int qy,int x,int pos,int l,int r){
      |                                                       ^
game.cpp:146:63: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
  146 | int qryseg(int qlx,int qrx,int qly,int qry,int pos,int l,int r){
      |                                                               ^
game.cpp:155:38: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
  155 | void update(int32_t P,int32_t Q,int x){
      |                                      ^
game.cpp:159:63: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
  159 | long long calculate(int32_t P, int32_t Q, int32_t U, int32_t V){
      |                                                               ^

• Subtask 1: 10 / 10
• Subtask 2: 27 / 27
• Subtask 3: 26 / 26
• Subtask 4: 17 / 17
• Subtask 5: 20 / 20