Submission #1013950

#	Time	Username	Problem	Language	Result	Execution time	Memory
1013950		amirhoseinfar1385	Game (IOI14_game)	C++17	100 / 100	254 ms	16720 KiB

game

#include "game.h"
#include<bits/stdc++.h>
using namespace std;
const int lg=14,maxn=(1<<lg),kaf=(1<<lg);

struct segment{
    struct node{
        int cnt,res;
        node(){
            cnt=res=0;
        }
    };
    node seg[(1<<(lg+1))];
    void insert(int i){
        i+=kaf;
        seg[i].cnt++;
        i>>=1;
        while(i>0){
            seg[i].cnt++;
            seg[i].res=seg[(i<<1)].cnt*seg[(i<<1)^1].cnt;
            i>>=1;
        }
        return ;
    }
    int pors(int i,int l,int r,int tl,int tr){
        if(!(tl>=l&&tr<=r)){
            return 0;
        }
        int m=(l+r)>>1;
        if(tl<=m&&tr>m){
            if(seg[i].res==1){
                return 1;
            }else{
                seg[i].res--;
                return 0;
            }
        }
        return pors((i<<1),l,m,tl,tr)+pors((i<<1)^1,m+1,r,tl,tr);
    }    
}seg;

void initialize(int n) {
    for(int i=0;i<n;i++){
        seg.insert(i);
    }
}

int hasEdge(int u, int v) {
    if(u>v){
        swap(u,v);
    }
    return seg.pors(1,0,kaf-1,u,v);
}

• Subtask 1: 15 / 15
• Subtask 2: 27 / 27
• Subtask 3: 58 / 58