oj.uz

Submission #658380

# Submission time Handle Problem Language Result Execution time Memory
658380 2022-11-13T03:58:00 Z jamezzz Horses (IOI15_horses) C++17
100 / 100
 1144 ms 204944 KB 
#include "horses.h"
#include <bits/stdc++.h>
using namespace std;

#define fi first
#define se second
typedef long long ll;
typedef pair<int,int> ii;
#define mod 1000000007

struct node{
	int s,e,m;ll v=1,lz=1;
	node *l,*r;
	node(int _s,int _e){
		s=_s,e=_e,m=(s+e)>>1;
		if(s!=e)l=new node(s,m),r=new node(m+1,e);
	}
	inline void ppo(){
		if(lz==1)return;
		v=(v*lz)%mod;
		if(s!=e){
			l->lz=(lz*l->lz)%mod;
			r->lz=(lz*r->lz)%mod;
		}
		lz=1;
	}
	void up(int x,int y,ll nv){
		if(s==x&&e==y){lz=(lz*nv)%mod;return;}
		if(y<=m)l->up(x,y,nv);
		else if(x>m)r->up(x,y,nv);
		else l->up(x,m,nv),r->up(m+1,y,nv);
		l->ppo(),r->ppo();
		v=max(l->v,r->v);
	}
	ll qry(int x,int y){
		ppo();
		if(s==x&&e==y)return v;
		if(y<=m)return l->qry(x,y);
		if(x>m)return r->qry(x,y);
		return max(l->qry(x,m),r->qry(m+1,y));
	}
}*rt;

struct node2{
	int s,e,m;ll v=1,lz=1;
	node2 *l,*r;
	node2(int _s,int _e){
		s=_s,e=_e,m=(s+e)>>1;
		if(s!=e)l=new node2(s,m),r=new node2(m+1,e);
	}
	inline void ppo(){
		if(lz==1)return;
		v=(v*lz)%mod;
		if(s!=e){
			l->lz=(lz*l->lz)%mod;
			r->lz=(lz*r->lz)%mod;
		}
		lz=1;
	}
	void up(int x,int y,ll nv){
		if(s==x&&e==y){lz=(lz*nv)%mod;return;}
		if(y<=m)l->up(x,y,nv);
		else if(x>m)r->up(x,y,nv);
		else l->up(x,m,nv),r->up(m+1,y,nv);
		l->ppo(),r->ppo();
		v=(l->v*r->v)%mod;
	}
	ll qry(int x,int y){
		ppo();
		if(s==x&&e==y)return v;
		if(y<=m)return l->qry(x,y);
		if(x>m)return r->qry(x,y);
		return (l->qry(x,m)*r->qry(m+1,y))%mod;
	}
}*pfx;

struct node3{
	int s,e,m,v;
	node3 *l,*r;
	node3(int _s,int _e){
		s=_s,e=_e,m=(s+e)>>1,v=0;
		if(s!=e)l=new node3(s,m),r=new node3(m+1,e);
	}
	void up(int x,ll nv){
		if(s==x&&e==x){v=nv;return;}
		if(x<=m)l->up(x,nv);
		else r->up(x,nv);
		v=max(l->v,r->v);
	}
	ll qry(int x,int y){
		if(s==x&&e==y)return v;
		if(y<=m)return l->qry(x,y);
		if(x>m)return r->qry(x,y);
		return max(l->qry(x,m),r->qry(m+1,y));
	}
}*yrt;

ll fp(ll x,int a){
	if(a==0)return 1;
	ll t=fp(x,a/2);
	ll r=(t*t)%mod;
	if(a%2)r=(r*x)%mod;
	return r;
}

#define maxn 500005
int n,x[maxn],y[maxn];
set<ii> s;

int ans(){
	auto it=s.end();
	ll mx=1;
	int pv=n;
	while(it!=s.begin()){
		--it;
		auto[i,x]=*it;
		//check if [i,n-1] can be >1e9
		mx=max(mx,yrt->qry(i,pv-1));
		mx*=x;
		if(mx>1e9){
			if(i==0)return mx%mod;
			ll f=pfx->qry(0,i-1);
			return (f*(mx%mod))%mod;
		}
		pv=i;
	}
	return rt->qry(0,n-1);
}

int init(int N,int X[],int Y[]){
	n=N;
	rt=new node(0,n-1);
	pfx=new node2(0,n-1);
	yrt=new node3(0,n-1);
	for(int i=0;i<n;++i){
		x[i]=X[i],y[i]=Y[i];
		rt->up(i,n-1,x[i]);
		pfx->up(i,i,x[i]);
		rt->up(i,i,y[i]);
		yrt->up(i,y[i]);
		if(x[i]!=1)s.insert({i,x[i]});
	}
	return ans();
}

int updateX(int pos,int val){	
	if(x[pos]!=1)s.erase({pos,x[pos]});
	rt->up(pos,n-1,fp(x[pos],mod-2));
	pfx->up(pos,pos,fp(x[pos],mod-2));
	rt->up(pos,n-1,val);
	pfx->up(pos,pos,val);
	x[pos]=val;
	if(val!=1)s.insert({pos,val});
	return ans();
}

int updateY(int pos,int val){
	rt->up(pos,pos,fp(y[pos],mod-2));
	rt->up(pos,pos,val);
	yrt->up(pos,val);
	y[pos]=val;
	return ans();
}

Compilation message

horses.cpp: In member function 'void node3::up(int, ll)':
horses.cpp:85:20: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   85 |   if(s==x&&e==x){v=nv;return;}
      |                    ^~
horses.cpp: In function 'int ans()':
horses.cpp:116:10: warning: declaration of 'x' shadows a global declaration [-Wshadow]
  116 |   auto[i,x]=*it;
      |          ^
horses.cpp:107:7: note: shadowed declaration is here
  107 | int n,x[maxn],y[maxn];
      |       ^
horses.cpp:120:6: warning: conversion from 'll' {aka 'long long int'} to 'double' may change value [-Wconversion]
  120 |   if(mx>1e9){
      |      ^~
horses.cpp:121:21: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  121 |    if(i==0)return mx%mod;
      |                     ^
horses.cpp:123:23: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  123 |    return (f*(mx%mod))%mod;
      |                       ^
horses.cpp:127:16: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  127 |  return rt->qry(0,n-1);
      |         ~~~~~~~^~~~~~~

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Correct 1 ms 212 KB Output is correct
19 Correct 0 ms 212 KB Output is correct
20 Correct 1 ms 212 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Correct 1 ms 212 KB Output is correct
19 Correct 0 ms 212 KB Output is correct
20 Correct 1 ms 212 KB Output is correct
21 Correct 0 ms 212 KB Output is correct
22 Correct 1 ms 212 KB Output is correct
23 Correct 2 ms 596 KB Output is correct
24 Correct 2 ms 596 KB Output is correct
25 Correct 2 ms 724 KB Output is correct
26 Correct 2 ms 724 KB Output is correct
27 Correct 3 ms 724 KB Output is correct
28 Correct 2 ms 724 KB Output is correct
29 Correct 2 ms 596 KB Output is correct
30 Correct 3 ms 724 KB Output is correct
31 Correct 2 ms 596 KB Output is correct
32 Correct 4 ms 596 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 994 ms 204884 KB Output is correct
2 Correct 1092 ms 204864 KB Output is correct
3 Correct 1084 ms 204816 KB Output is correct
4 Correct 1136 ms 204876 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 312 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 308 KB Output is correct
10 Correct 1 ms 300 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 1 ms 312 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Correct 1 ms 212 KB Output is correct
19 Correct 1 ms 212 KB Output is correct
20 Correct 0 ms 212 KB Output is correct
21 Correct 1 ms 308 KB Output is correct
22 Correct 1 ms 212 KB Output is correct
23 Correct 2 ms 712 KB Output is correct
24 Correct 2 ms 596 KB Output is correct
25 Correct 2 ms 704 KB Output is correct
26 Correct 2 ms 708 KB Output is correct
27 Correct 3 ms 596 KB Output is correct
28 Correct 2 ms 708 KB Output is correct
29 Correct 2 ms 596 KB Output is correct
30 Correct 3 ms 748 KB Output is correct
31 Correct 2 ms 712 KB Output is correct
32 Correct 3 ms 596 KB Output is correct
33 Correct 470 ms 180688 KB Output is correct
34 Correct 466 ms 180660 KB Output is correct
35 Correct 678 ms 204000 KB Output is correct
36 Correct 660 ms 204048 KB Output is correct
37 Correct 518 ms 180664 KB Output is correct
38 Correct 565 ms 192472 KB Output is correct
39 Correct 449 ms 180436 KB Output is correct
40 Correct 638 ms 203936 KB Output is correct
41 Correct 422 ms 180560 KB Output is correct
42 Correct 439 ms 180448 KB Output is correct
43 Correct 627 ms 204096 KB Output is correct
44 Correct 654 ms 204080 KB Output is correct

Subtask #5
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 312 KB Output is correct
6 Correct 1 ms 312 KB Output is correct
7 Correct 1 ms 312 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 1 ms 308 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 1 ms 212 KB Output is correct
17 Correct 1 ms 316 KB Output is correct
18 Correct 0 ms 212 KB Output is correct
19 Correct 1 ms 212 KB Output is correct
20 Correct 1 ms 212 KB Output is correct
21 Correct 1 ms 212 KB Output is correct
22 Correct 1 ms 212 KB Output is correct
23 Correct 2 ms 596 KB Output is correct
24 Correct 3 ms 596 KB Output is correct
25 Correct 3 ms 704 KB Output is correct
26 Correct 3 ms 708 KB Output is correct
27 Correct 3 ms 704 KB Output is correct
28 Correct 3 ms 724 KB Output is correct
29 Correct 3 ms 596 KB Output is correct
30 Correct 3 ms 724 KB Output is correct
31 Correct 2 ms 576 KB Output is correct
32 Correct 2 ms 596 KB Output is correct
33 Correct 823 ms 204924 KB Output is correct
34 Correct 1068 ms 204912 KB Output is correct
35 Correct 1047 ms 204912 KB Output is correct
36 Correct 1144 ms 204844 KB Output is correct
37 Correct 469 ms 180592 KB Output is correct
38 Correct 446 ms 180724 KB Output is correct
39 Correct 656 ms 204016 KB Output is correct
40 Correct 657 ms 204160 KB Output is correct
41 Correct 466 ms 180672 KB Output is correct
42 Correct 567 ms 192424 KB Output is correct
43 Correct 430 ms 180416 KB Output is correct
44 Correct 645 ms 204076 KB Output is correct
45 Correct 426 ms 180536 KB Output is correct
46 Correct 435 ms 180560 KB Output is correct
47 Correct 640 ms 203900 KB Output is correct
48 Correct 621 ms 203964 KB Output is correct
49 Correct 781 ms 182620 KB Output is correct
50 Correct 763 ms 182556 KB Output is correct
51 Correct 787 ms 204888 KB Output is correct
52 Correct 762 ms 204908 KB Output is correct
53 Correct 867 ms 182604 KB Output is correct
54 Correct 719 ms 195488 KB Output is correct
55 Correct 578 ms 180880 KB Output is correct
56 Correct 808 ms 204944 KB Output is correct
57 Correct 559 ms 181396 KB Output is correct
58 Correct 620 ms 181532 KB Output is correct
59 Correct 620 ms 203948 KB Output is correct