제출 #442355

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
442355		FEDIKUS	말 (IOI15_horses)	C++17	100 / 100	1074 ms	32196 KiB

horses

#include "horses.h"

#include<bits/stdc++.h>
#define mp make_pair

using namespace std;

typedef long long ll;

const int maxn=5e5+10;
const int mod=1e9+7;
int n;
int bseg[4*maxn];
int y[maxn];
pair<bool,int> pseg[4*maxn];

pair<bool,int> comb(pair<bool,int> a,pair<bool,int> b){
    if(a.first || b.first){
        return mp(true,ll(a.second)*ll(b.second)%mod);
    }
    if(ll(a.second)*ll(b.second)>=mod){
        return mp(true,ll(a.second)*ll(b.second)%mod);
    }
    return mp(false,ll(a.second)*ll(b.second));
}

void buildp(int *x,int ind=1,int l=0,int r=n-1){
    if(l==r){
        pseg[ind]={false,x[l]};
        return;
    }
    int mid=l+(r-l)/2;
    buildp(x,2*ind,l,mid);
    buildp(x,2*ind+1,mid+1,r);
    pseg[ind]=comb(pseg[2*ind],pseg[2*ind+1]);
}

void updatep(int t,int v,int ind=1,int l=0,int r=n-1){
    if(l==r){
        pseg[ind]={false,v};
        return;
    }
    int mid=l+(r-l)/2;
    if(t<=mid) updatep(t,v,2*ind,l,mid);
    if(t>mid) updatep(t,v,2*ind+1,mid+1,r);
    pseg[ind]=comb(pseg[2*ind],pseg[2*ind+1]);
}

pair<bool,int> queryp(int tl,int tr,int ind=1,int l=0,int r=n-1){
    if(tl<=l && r<=tr) return pseg[ind];
    int mid=l+(r-l)/2;
    pair<bool,int> ret={false,1};
    if(tl<=mid) ret=comb(ret,queryp(tl,tr,2*ind,l,mid));
    if(tr>mid) ret=comb(ret,queryp(tl,tr,2*ind+1,mid+1,r));
    return ret;
}

int comp(int a,int b){
    if(a>b) swap(a,b);
    pair<bool,int> raz=queryp(a+1,b);
    raz=comb(raz,mp(false,y[b]));
    if(raz.first) return b;
    if(raz.second>y[a]) return b;
    else return a;
}

void buildb(int ind=1,int l=0,int r=n-1){
    if(l==r){
        bseg[ind]=l;
        return;
    }
    int mid=l+(r-l)/2;
    buildb(2*ind,l,mid);
    buildb(2*ind+1,mid+1,r);
    bseg[ind]=comp(bseg[2*ind],bseg[2*ind+1]);
}

void updateb(int t,int ind=1,int l=0,int r=n-1){
    if(l==r) return;
    int mid=l+(r-l)/2;
    if(t<=mid) updateb(t,2*ind,l,mid);
    if(t>mid) updateb(t,2*ind+1,mid+1,r);
    bseg[ind]=comp(bseg[2*ind],bseg[2*ind+1]);
}

int init(int N, int X[], int Y[]) {
	n=N;
	for(int i=0;i<n;i++) y[i]=Y[i];
	buildp(X);
	buildb();
	return comb(queryp(0,bseg[1]),mp(false,y[bseg[1]])).second;
}

int updateX(int pos, int val) {
    updatep(pos,val);
    updateb(pos);
	return comb(queryp(0,bseg[1]),mp(false,y[bseg[1]])).second;
}

int updateY(int pos, int val) {
    y[pos]=val;
    updateb(pos);
	return comb(queryp(0,bseg[1]),mp(false,y[bseg[1]])).second;
}
/*
3
2 1 3
3 4 1
1
2 1 2
*/

• Subtask 1: 17 / 17
• Subtask 2: 17 / 17
• Subtask 3: 20 / 20
• Subtask 4: 23 / 23
• Subtask 5: 23 / 23