Submission #1030271

#	Time	Username	Problem	Language	Result	Execution time	Memory
1030271		pcc	Horses (IOI15_horses)	C++17	34 / 100	1562 ms	24944 KiB

horses

#include "horses.h"
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define pll pair<ll,ll>
#define fs first
#define sc second
const ll mod = 1e9+7;
const ll mxn = 5e5+10;

ll pref[mxn];
ll N;
ll arr[mxn],brr[mxn];
set<int> st;

struct SEG{
#define ls now*2+1
#define rs now*2+2
#define mid ((l+r)>>1)
	ll seg[mxn*4];
	void build(int now,int l,int r){
		if(l == r){
			seg[now] = arr[l];
			return;
		}
		build(ls,l,mid);
		build(rs,mid+1,r);
		seg[now] = seg[ls]*seg[rs];
		if(seg[now]>=mod)seg[now] = mod+seg[now]%mod;
		return;
	}
	void modify(int now,int l,int r,int p,ll v){
		if(l == r){
			seg[now] = v;
			return;
		}
		if(mid>=p)modify(ls,l,mid,p,v);
		else modify(rs,mid+1,r,p,v);
		seg[now] = seg[ls]*seg[rs];
		if(seg[now]>=mod)seg[now] = mod+seg[now]%mod;
	}
	ll getval(int now,int l,int r,int s,int e){
		if(l>=s&&e>=r)return seg[now];
		if(mid>=e)return getval(ls,l,mid,s,e);
		else if(mid<s)return getval(rs,mid+1,r,s,e);
		else{
			auto re = getval(ls,l,mid,s,e)*getval(rs,mid+1,r,s,e);
			if(re>=mod)return mod+re%mod;
			else return re;
		}
	}
#undef ls
#undef rs
#undef mid
};

SEG seg;

bool cmp(int a,int b){
	if(a>b)return brr[a]*seg.getval(0,0,N-1,b+1,a)<brr[b];
	else return brr[a]<brr[b]*seg.getval(0,0,N-1,a+1,b);
}

ll getans(){
	vector<int> v(N);
	iota(v.begin(),v.end(),0);
	sort(v.begin(),v.end(),cmp);
	return seg.getval(0,0,N-1,0,v.back())*brr[v.back()]%mod;
}

int init(int NN, int X[], int Y[]) {
	N = NN;
	for(int i = 0;i<N;i++){
		arr[i] = X[i];
		brr[i] = Y[i];
	}
	seg.build(0,0,N-1);
	return getans();
}

int updateX(int pos, int val) {	
	seg.modify(0,0,N-1,pos,arr[pos]=val);
	return getans();
}

int updateY(int pos, int val) {
	brr[pos] = val;
	return getans();
}

Compilation message (stderr)

horses.cpp: In function 'bool cmp(int, int)':
horses.cpp:61:39: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   61 |  if(a>b)return brr[a]*seg.getval(0,0,N-1,b+1,a)<brr[b];
      |                                      ~^~
horses.cpp:62:44: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   62 |  else return brr[a]<brr[b]*seg.getval(0,0,N-1,a+1,b);
      |                                           ~^~
horses.cpp: In function 'long long int getans()':
horses.cpp:69:25: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   69 |  return seg.getval(0,0,N-1,0,v.back())*brr[v.back()]%mod;
      |                        ~^~
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:78:17: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   78 |  seg.build(0,0,N-1);
      |                ~^~
horses.cpp:79:15: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   79 |  return getans();
      |         ~~~~~~^~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:83:18: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   83 |  seg.modify(0,0,N-1,pos,arr[pos]=val);
      |                 ~^~
horses.cpp:84:15: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   84 |  return getans();
      |         ~~~~~~^~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:89:15: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   89 |  return getans();
      |         ~~~~~~^~

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