Submission #603257

#	Time	Username	Problem	Language	Result	Execution time	Memory
603257		chirathnirodha	Horses (IOI15_horses)	C++17	0 / 100	1572 ms	61164 KiB

horses

#include "horses.h"
#include<bits/stdc++.h>
using namespace std;
#define PB push_back
#define MP make_pair
#define P push
#define I insert
#define F first
#define S second
typedef long long ll;
const ll mod=1e9+7;
const int maxn=500000;
int n;
ll segx[4*maxn],segy[4*maxn];
ll co[maxn],pr[maxn];
set<int> notone;
ll expo(ll x,ll y){
	if(y==0)return 1;
	if(y%2==1)return (x*expo((x*x)%mod,y/2))%mod;
	else return expo(x*x,y/2);
}
void updx(ll a,ll b,int c,ll x,ll px,int y){
	segx[c]=(segx[c]%mod*expo(px,mod-2)%mod)%mod;
	segx[c]*=x;segx[c]%=mod;
	if(a==b)return;
	ll m=(a+b)/2;
	if(y<=m)updx(a,m,2*c,x,px,y);
	else updx(m+1,b,2*c+1,x,px,y);
}
ll findx(ll a,ll b,ll c,ll x,ll y){
	if(a==x && b==y)return segx[c];
	ll m=(a+b)/2;
	if(y<=m)return findx(a,m,2*c,x,y);
	if(x>=m+1)return findx(m+1,b,2*c+1,x,y);
	return (findx(a,m,2*c,x,m)*findx(m+1,b,2*c+1,m+1,y))%mod;
}
void updy(ll a,ll b,int c,ll x,int y){
	if(a==b){
		segy[c]=x;
		return;
	}
	ll m=(a+b)/2;
	if(y<=m)updy(a,m,2*c,x,y);
	else updy(m+1,b,2*c+1,x,y);
	segy[c]=max(segy[2*c],segy[2*c+1]);
}
ll findy(ll a,ll b,ll c,ll x,ll y){
	if(a==x && b==y)return segy[c];
	ll m=(a+b)/2;
	if(y<=m)return findy(a,m,2*c,x,y);
	if(x>=m+1)return findy(m+1,b,2*c+1,x,y);
	return max(findy(a,m,2*c,x,m),findy(m+1,b,2*c+1,m+1,y));
}
int func(){
	auto itr=notone.end();itr--;
	int last=*itr;itr--;
	vector<pair<ll,ll> > v;
	while(true){
		if(v.size()>=80)break;
		int cur=*itr;
		if(cur+1!=last)v.PB(MP(last-1,findy(0,n-1,1,cur+1,last-1)));
		if(cur==-1)break;
		v.PB(MP(cur,pr[cur]));
		last=cur;
		itr--;
	}
	reverse(v.begin(),v.end());
	int cmax=0;
	ll mul=1;
	for(int i=1;i<v.size();i++){
		mul*=co[v[i].F];
		if(mul*v[i].S>v[cmax].S){
			cmax=i;
			mul=1;
		}
	}
	ll ans=v[cmax].S;
	ans=v[cmax].S*findx(0,n-1,1,0,v[cmax].F);
	ans%=mod;
	return ans;
}
int init(int N, int X[], int Y[]) {
	n=N;
	for(int i=0;i<4*n;i++){segx[i]=1;segy[i]=0;}
	for(int i=0;i<n;i++){
		co[i]=X[i];
		pr[i]=Y[i];
		updy(0,n-1,1,Y[i],i);
		updx(0,n-1,1,X[i],1,i);
	}
	for(int i=0;i<12;i++)cout<<segx[i]<<" ";cout<<endl;
	for(int i=0;i<12;i++)cout<<segy[i]<<" ";cout<<endl;
	cout<<endl;
	notone.I(-1);notone.I(n);
	for(int i=0;i<n;i++)if(X[i]!=1)notone.I(i);
	return func();
}

int updateX(int pos, int val) {	
	updx(0,n-1,1,val,co[pos],pos);
	co[pos]=val;
	if(val==1)notone.erase(pos);
	else notone.I(pos);
	for(int i=0;i<12;i++)cout<<segx[i]<<" ";cout<<endl;
	for(int i=0;i<12;i++)cout<<segy[i]<<" ";cout<<endl;
	cout<<endl;
	return func();
}

int updateY(int pos, int val) {
	updy(0,n-1,1,val,pos);
	pr[pos]=val;
	for(int i=0;i<12;i++)cout<<segx[i]<<" ";cout<<endl;
	for(int i=0;i<12;i++)cout<<segy[i]<<" ";cout<<endl;
	cout<<"UPY"<<endl;
	return func();
}

Compilation message (stderr)

horses.cpp: In function 'int func()':
horses.cpp:70:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   70 |  for(int i=1;i<v.size();i++){
      |              ~^~~~~~~~~
horses.cpp:80:9: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   80 |  return ans;
      |         ^~~
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:91:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   91 |  for(int i=0;i<12;i++)cout<<segx[i]<<" ";cout<<endl;
      |  ^~~
horses.cpp:91:42: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   91 |  for(int i=0;i<12;i++)cout<<segx[i]<<" ";cout<<endl;
      |                                          ^~~~
horses.cpp:92:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   92 |  for(int i=0;i<12;i++)cout<<segy[i]<<" ";cout<<endl;
      |  ^~~
horses.cpp:92:42: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   92 |  for(int i=0;i<12;i++)cout<<segy[i]<<" ";cout<<endl;
      |                                          ^~~~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:104:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  104 |  for(int i=0;i<12;i++)cout<<segx[i]<<" ";cout<<endl;
      |  ^~~
horses.cpp:104:42: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  104 |  for(int i=0;i<12;i++)cout<<segx[i]<<" ";cout<<endl;
      |                                          ^~~~
horses.cpp:105:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  105 |  for(int i=0;i<12;i++)cout<<segy[i]<<" ";cout<<endl;
      |  ^~~
horses.cpp:105:42: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  105 |  for(int i=0;i<12;i++)cout<<segy[i]<<" ";cout<<endl;
      |                                          ^~~~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:113:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  113 |  for(int i=0;i<12;i++)cout<<segx[i]<<" ";cout<<endl;
      |  ^~~
horses.cpp:113:42: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  113 |  for(int i=0;i<12;i++)cout<<segx[i]<<" ";cout<<endl;
      |                                          ^~~~
horses.cpp:114:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  114 |  for(int i=0;i<12;i++)cout<<segy[i]<<" ";cout<<endl;
      |  ^~~
horses.cpp:114:42: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  114 |  for(int i=0;i<12;i++)cout<<segy[i]<<" ";cout<<endl;
      |                                          ^~~~

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