Submission #1319200

#	Time	Username	Problem	Language	Result	Execution time	Memory
1319200		ghammazhassan	Horses (IOI15_horses)	C++20	100 / 100	733 ms	65180 KiB

horses

#include "horses.h"
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <map>
#include <unordered_map>
#include <vector>
#include <iomanip>
#include <string>
#include <queue>
#include <set>
#include <deque>
using namespace std;
#define ll long long
const ll M=1e9+7;
const int N=5e5+5;
static char _buffer[1024];
static int _currentChar = 0;
static int _charsNumber = 0;

int n;
int a[N];
int b[N];
struct pii
{
	ll vl=1;
	double vi=0;
};
pii lz[4*N];
struct node
{
	double mx=0;
	int pos=-1;
	ll pr=1;
};
ll bp(ll x,ll y){
	x%=M;
	if (y==0)return 1;
	if (y==1)return x;
	ll r=bp(x*x,y/2);
	if (y%2)r*=x;
	return r%M;
}
ll inv(ll x){
	return bp(x,M-2);
}
node seg[4*N];
node join(node x,node y){
	node r;
	r.mx=max(x.mx,y.mx);
	if (r.mx==x.mx)r.pos=x.pos;
	if (r.mx==y.mx)r.pos=y.pos;
	r.pr=(x.pr*y.pr)%M;
	return r;
}
void build(int s=0,int e=n,int v=1){
	if (e-s==1){
		seg[v].pos=s;
		seg[v].mx=log2(a[s]);
		seg[v].pr=a[s];
		return;
	}
	int li=2*v;
	int ri=2*v+1;
	int m=(s+e)/2;
	build(s,m,li);
	build(m,e,ri);
	seg[v]=join(seg[li],seg[ri]);
}
void lazy(int v,int f){
	ll x=lz[v].vl;
	lz[v].vl=1;
	seg[v].pr=(seg[v].pr*x)%M;
	double y=lz[v].vi;
	lz[v].vi=0;
	seg[v].mx+=y;
	if (f!=1){
		lz[2*v].vl=(lz[2*v].vl*x)%M;
		lz[2*v+1].vl=(lz[2*v+1].vl*x)%M;
		lz[2*v].vi+=y;
		lz[2*v+1].vi+=y;
	}
}
void update(int l,int r,int x,int s=0,int e=n,int v=1){
	lazy(v,e-s);
	if (l>=e or r<=s)return;
	if (l<=s and e<=r){
		lz[v].vl=(lz[v].vl*x)%M;
		lz[v].vi+=log2(x);
		lazy(v,e-s);
		return;
	}
	int li=2*v;
	int ri=2*v+1;
	int m=(s+e)/2;
	update(l,r,x,s,m,li);
	update(l,r,x,m,e,ri);
	seg[v]=join(seg[li],seg[ri]);
}

void update1(int l,int r,int x,int s=0,int e=n,int v=1){
	lazy(v,e-s);
	if (l>=e or r<=s)return;
	if (l<=s and e<=r){
		lz[v].vl=(lz[v].vl*inv(x))%M;
		lz[v].vi-=log2(x);
		lazy(v,e-s);
		return;
	}
	int li=2*v;
	int ri=2*v+1;
	int m=(s+e)/2;
	update1(l,r,x,s,m,li);
	update1(l,r,x,m,e,ri);
	seg[v]=join(seg[li],seg[ri]);
}
node query(int l,int r,int s=0,int e=n,int v=1){
	lazy(v,e-s);
	if (l>=e or r<=s)return node();
	if (l<=s and e<=r)return seg[v];
	int li=2*v;
	int ri=2*v+1;
	int m=(s+e)/2;
	node p=join(query(l,r,s,m,li),query(l,r,m,e,ri));
	seg[v]=join(seg[li],seg[ri]);
	return p;
}
int init(int K,int x[],int y[]){
	n=K;
	for (int i=0;i<4*N;i++){
		lz[i].vl=1;
	}
	for (int i=0;i<n;i++){
		a[i]=y[i];
	}
	for (int i=0;i<n;i++){
		b[i]=x[i];
	}
	build();
	for (int i=0;i<n;i++){
		update(i,n,x[i]);
	}
	int po=query(0,n).pos;
	return query(po,po+1).pr;
}
int updateX(int i,int x){
	update1(i,n,b[i]);
	b[i]=x;
	update(i,n,b[i]);
	int po=query(0,n).pos;
	return query(po,po+1).pr;
}
int updateY(int i,int x){
	update1(i,i+1,a[i]);
	a[i]=x;
	update(i,i+1,a[i]);
	int po=query(0,n).pos;
	return query(po,po+1).pr;
}

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