Submission #1167086

#	Time	Username	Problem	Language	Result	Execution time	Memory
1167086		8pete8	Game (IOI13_game)	C++20	37 / 100	13090 ms	5412 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;
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->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[mxn+10];
void init(int32_t R, int32_t C){
    return;
}
void print(node *&x){
    if(x==NULL)return;
    cout<<x->val<<" "<<x->G<<"P\n";
}
void update(int32_t P, int32_t Q, long long K){
    node *x=new node(P,Q,K);
    if(row[P].root==NULL)row[P].root=x;
    else{
        node *R=NULL;
        row[P].split(row[P].root,R,row[P].root,P,Q);
        if(row[P].change(row[P].root,P,Q,K))return void(row[P].merge(row[P].root,R,row[P].root));

        row[P].merge(row[P].root,x,row[P].root);
        row[P].merge(row[P].root,R,row[P].root);
    }
}
//col U->V
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;
}
long long calculate(int32_t P, int32_t Q, int32_t U, int32_t V){
    int ans=0;
    for(int i=P;i<=U;i++)ans=gcd(ans,get(i,Q,V));
    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:104:31: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
  104 | void init(int32_t R, int32_t C){
      |                               ^
game.cpp:107:20: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
  107 | void print(node *&x){
      |                    ^
game.cpp:111:46: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
  111 | void update(int32_t P, int32_t Q, long long K){
      |                                              ^
game.cpp:124:26: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
  124 | int get(int x,int U,int V){
      |                          ^
game.cpp:134:63: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
  134 | 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: 0 / 26
• Subtask 4: 0 / 17
• Subtask 5: 0 / 20