Submission #65371

#	Time	Username	Problem	Language	Result	Execution time	Memory
65371		hamzqq9	Horses (IOI15_horses)	C++14	17 / 100	459 ms	44272 KiB

horses

#include "horses.h"
#include<bits/stdc++.h>
using namespace std;
#define MOD 1000000007
#define st first
#define nd second
#define orta ((bas+son)>>1)
#define ii pair<int,int>
#define pb push_back
#define all(x) x.begin(),x.end()
#define ll long long


struct day {

	int l,r;
	int xpro;
	int mxy;

	day(int a,int b,int c,int d) {

		l=a;r=b;xpro=c;mxy=d;

	}

	bool operator<(const day& oth) const {

		return r<oth.r;

	}

	bool operator>(const day& oth) const {

		return r>oth.r;

	}

};

set<day> S;
int N;
int X[500005];
int seg[500005*4],tut[500005];
int allpro=1;

int fe(int x,int y) {

	int res=1;
	int cur=x;

	while(y) {

		if(y&1) res=1ll*res*cur%MOD;

		y>>=1;

		cur=1ll*cur*cur%MOD;

	}

	return res;

}

int get(int node,int bas,int son,int x,int y) {

	if(bas>=x && son<=y) return seg[node];

	if(orta>=x && orta+1<=y) return max(get(node*2,bas,orta,x,y),get(node*2+1,orta+1,son,x,y));
	if(orta>=x) return get(node*2,bas,orta,x,y);
	if(orta+1<=y) return get(node*2+1,orta+1,son,x,y);

}

void up(int pos,int val) {

	seg[tut[pos]]=val;

	for(int node=tut[pos]>>1;node>=1;node>>=1) {

		seg[node]=max(seg[node<<1],seg[(node<<1)|1]);

	}

}

void build(int node,int bas,int son,int Y[]) {

	if(bas==son) {

		seg[node]=Y[bas];
		tut[bas]=node;

		return ;

	}

	build(node*2,bas,orta,Y);
	build(node*2+1,orta+1,son,Y);

	seg[node]=max(seg[node*2],seg[node*2+1]);

}

int get_ans() {

	vector< ii > v;

	int tot=0;

	auto it=S.end();

	it--;

	while(tot++<32) {

		v.pb({it->xpro,it->mxy});

//		printf("%dth xpro-->%d mxy-->%d\n",tot-1,v.back().st,v.back().nd);

		if(it==S.begin()) break ;

		it--;

	}

	reverse(all(v));

	int best_ind=0;

	for(int i=0;i<tot;i++) {

		int tut=i;

		while(i+1<tot && v[i+1].st==1) i++;

		assert(i-tut+1<=1);

	}

	for(int i=0;i<tot;i++) {

		int ind=i;
		ll curpro=1;

		while(i+1<tot) {

			ll val=1ll*v[i+1].st*v[i+1].nd;

			if(val<v[ind].nd && curpro*val<v[ind].nd) {

				curpro*=v[i+1].st;

				i++;

				continue ;

			}

			break ;

		}

		if(i==tot-1) {

			best_ind=ind;

			break ;

		}

	}

	int dv=1;

	for(int i=tot-1;i>best_ind;i--) {

		dv=1ll*dv*v[i].st%MOD;

	}

	return 1ll*fe(dv,MOD-2)*allpro%MOD*v[best_ind].nd%MOD;

}

int init(int N, int X[], int Y[]) {
	
	::N=N;

	for(int i=0;i<N;i++) {

		::X[i]=X[i];

		day cur(i,i,X[i],Y[i]);

		while(i+1<N && X[i+1]==1) {

			i++;

			cur.r=i;
			cur.mxy=max(cur.mxy,Y[i]);

			::X[i]=X[i];

		}

		S.insert(cur);

		allpro=1ll*allpro*cur.xpro%MOD;

	}

	build(1,0,N-1,Y);

	return get_ans();

}

int updateX(int pos, int val) {	
	
	allpro=1ll*allpro*fe(X[pos],MOD-2)%MOD;

	allpro=1ll*allpro*val%MOD;

	if(X[pos]==1 && val!=1) {

		day cur(pos,pos,0,0);

		auto _pos=S.lower_bound(cur);

		cur=*_pos;

		S.erase(_pos);

		day l(cur.l,pos-1,cur.xpro,(cur.l>pos?0:get(1,0,N-1,cur.l,pos-1)));
		day r(pos,cur.r,val,get(1,0,N-1,pos,cur.r));

		if(cur.l<=pos) S.insert(l);
		S.insert(r);

	}

	if(X[pos]>1 && val==1) {

		day cur(pos,pos,0,0);

		auto _pos=S.lower_bound(cur);

		if(_pos==S.begin()) {

			cur=*_pos;

			S.erase(_pos);

			cur.xpro=1;

			S.insert(cur);

		}
		else {

			day cur2=*_pos;

			S.erase(_pos--);

			day cur1=*_pos;

			S.erase(_pos);

			day nw(cur1.l,cur2.r,cur1.xpro,max(cur1.mxy,cur2.mxy));

			S.insert(nw);

		}

	}

	if(X[pos]>1 && val>1) {

		day cur(pos,pos,0,0);

		auto _pos=S.lower_bound(cur);

		cur=*_pos;

		S.erase(_pos);

		cur.xpro=val;

		S.insert(cur);

	}

	X[pos]=val;

	return get_ans();

}

int updateY(int pos, int val) {
	
	up(pos,val);

	day cur(pos,pos,0,0);

	auto _pos=S.lower_bound(cur);

	cur=*_pos;

	S.erase(_pos);

	cur.mxy=get(1,0,N-1,cur.l,cur.r);

	S.insert(cur);

	return get_ans();

}

Compilation message (stderr)

horses.cpp: In function 'int fe(int, int)':
horses.cpp:53:26: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
   if(y&1) res=1ll*res*cur%MOD;
                          ^
horses.cpp:57:18: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
   cur=1ll*cur*cur%MOD;
                  ^
horses.cpp: In function 'int get_ans()':
horses.cpp:133:7: warning: declaration of 'tut' shadows a global declaration [-Wshadow]
   int tut=i;
       ^~~
horses.cpp:43:19: note: shadowed declaration is here
 int seg[500005*4],tut[500005];
                   ^~~
horses.cpp:178:20: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
   dv=1ll*dv*v[i].st%MOD;
                    ^
horses.cpp:182:51: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
  return 1ll*fe(dv,MOD-2)*allpro%MOD*v[best_ind].nd%MOD;
                                                   ^
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:186:33: warning: declaration of 'X' shadows a global declaration [-Wshadow]
 int init(int N, int X[], int Y[]) {
                                 ^
horses.cpp:42:5: note: shadowed declaration is here
 int X[500005];
     ^
horses.cpp:186:33: warning: declaration of 'N' shadows a global declaration [-Wshadow]
 int init(int N, int X[], int Y[]) {
                                 ^
horses.cpp:41:5: note: shadowed declaration is here
 int N;
     ^
horses.cpp:209:29: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
   allpro=1ll*allpro*cur.xpro%MOD;
                             ^
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:221:36: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
  allpro=1ll*allpro*fe(X[pos],MOD-2)%MOD;
                                    ^
horses.cpp:223:23: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
  allpro=1ll*allpro*val%MOD;
                       ^
horses.cpp: In function 'int get(int, int, int, int, int)':
horses.cpp:73:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

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