oj.uz

Submission #658379

# Submission time Handle Problem Language Result Execution time Memory
658379 2022-11-13T03:54:35 Z jamezzz Horses (IOI15_horses) C++17
80 / 100
 1500 ms 217516 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);
	}
	void ppo(){
		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));
	}
	void print(){
		printf("%d %d %d %lld %lld\n",s,e,m,v,lz);
		if(s!=e)l->print(),r->print();
	}
}*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);
	}
	void ppo(){
		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;
	}
	void print(){
		printf("%d %d %d %lld %lld\n",s,e,m,v,lz);
		if(s!=e)l->print(),r->print();
	}
}*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));
	}
	void print(){
		printf("%d %d %d %lld\n",s,e,m,v);
		if(s!=e)l->print(),r->print();
	}
}*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:91:20: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   91 |   if(s==x&&e==x){v=nv;return;}
      |                    ^~
horses.cpp: In member function 'void node3::print()':
horses.cpp:103:23: warning: format '%lld' expects argument of type 'long long int', but argument 5 has type 'int' [-Wformat=]
  103 |   printf("%d %d %d %lld\n",s,e,m,v);
      |                    ~~~^          ~
      |                       |          |
      |                       |          int
      |                       long long int
      |                    %d
horses.cpp: In function 'int ans()':
horses.cpp:126:10: warning: declaration of 'x' shadows a global declaration [-Wshadow]
  126 |   auto[i,x]=*it;
      |          ^
horses.cpp:117:7: note: shadowed declaration is here
  117 | int n,x[maxn],y[maxn];
      |       ^
horses.cpp:130:6: warning: conversion from 'll' {aka 'long long int'} to 'double' may change value [-Wconversion]
  130 |   if(mx>1e9){
      |      ^~
horses.cpp:131:21: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  131 |    if(i==0)return mx%mod;
      |                     ^
horses.cpp:133:23: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  133 |    return (f*(mx%mod))%mod;
      |                       ^
horses.cpp:137:16: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  137 |  return rt->qry(0,n-1);
      |         ~~~~~~~^~~~~~~

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 316 KB Output is correct
3 Correct 1 ms 312 KB Output is correct
4 Correct 1 ms 316 KB Output is correct
5 Correct 1 ms 316 KB Output is correct
6 Correct 1 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 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 308 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 1 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 1 ms 212 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 308 KB Output is correct
6 Correct 1 ms 312 KB Output is correct
7 Correct 1 ms 308 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 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 0 ms 312 KB Output is correct
17 Correct 0 ms 212 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 308 KB Output is correct
21 Correct 1 ms 308 KB Output is correct
22 Correct 0 ms 212 KB Output is correct
23 Correct 3 ms 724 KB Output is correct
24 Correct 3 ms 724 KB Output is correct
25 Correct 3 ms 708 KB Output is correct
26 Correct 3 ms 724 KB Output is correct
27 Correct 3 ms 596 KB Output is correct
28 Correct 3 ms 704 KB Output is correct
29 Correct 3 ms 580 KB Output is correct
30 Correct 3 ms 708 KB Output is correct
31 Correct 3 ms 596 KB Output is correct
32 Correct 4 ms 596 KB Output is correct

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1143 ms 208640 KB Output is correct
2 Correct 1398 ms 217516 KB Output is correct
3 Correct 1374 ms 208792 KB Output is correct
4 Execution timed out 1519 ms 212440 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 316 KB Output is correct
2 Correct 1 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 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 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 1 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 0 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 316 KB Output is correct
16 Correct 1 ms 308 KB Output is correct
17 Correct 0 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 212 KB Output is correct
22 Correct 1 ms 312 KB Output is correct
23 Correct 3 ms 724 KB Output is correct
24 Correct 3 ms 712 KB Output is correct
25 Correct 4 ms 724 KB Output is correct
26 Correct 3 ms 724 KB Output is correct
27 Correct 4 ms 596 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 3 ms 596 KB Output is correct
32 Correct 3 ms 708 KB Output is correct
33 Correct 790 ms 184428 KB Output is correct
34 Correct 749 ms 184528 KB Output is correct
35 Correct 911 ms 214784 KB Output is correct
36 Correct 1008 ms 214696 KB Output is correct
37 Correct 764 ms 182752 KB Output is correct
38 Correct 801 ms 195316 KB Output is correct
39 Correct 729 ms 182340 KB Output is correct
40 Correct 900 ms 209928 KB Output is correct
41 Correct 722 ms 182504 KB Output is correct
42 Correct 832 ms 182404 KB Output is correct
43 Correct 881 ms 210120 KB Output is correct
44 Correct 895 ms 210208 KB Output is correct

Subtask #5
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 316 KB Output is correct
3 Correct 1 ms 312 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 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 0 ms 212 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 1 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 1 ms 212 KB Output is correct
21 Correct 1 ms 312 KB Output is correct
22 Correct 1 ms 212 KB Output is correct
23 Correct 3 ms 724 KB Output is correct
24 Correct 3 ms 724 KB Output is correct
25 Correct 4 ms 732 KB Output is correct
26 Correct 3 ms 728 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 692 KB Output is correct
32 Correct 3 ms 596 KB Output is correct
33 Correct 1153 ms 208552 KB Output is correct
34 Correct 1372 ms 217296 KB Output is correct
35 Correct 1369 ms 208484 KB Output is correct
36 Correct 1483 ms 212644 KB Output is correct
37 Correct 756 ms 184424 KB Output is correct
38 Correct 874 ms 184564 KB Output is correct
39 Correct 934 ms 214788 KB Output is correct
40 Correct 924 ms 214796 KB Output is correct
41 Correct 785 ms 182580 KB Output is correct
42 Correct 826 ms 195344 KB Output is correct
43 Correct 776 ms 182368 KB Output is correct
44 Correct 959 ms 209880 KB Output is correct
45 Correct 780 ms 182540 KB Output is correct
46 Correct 793 ms 182440 KB Output is correct
47 Correct 869 ms 210216 KB Output is correct
48 Correct 890 ms 210148 KB Output is correct
49 Correct 1106 ms 187504 KB Output is correct
50 Correct 1186 ms 187468 KB Output is correct
51 Correct 1114 ms 216648 KB Output is correct
52 Correct 1125 ms 216128 KB Output is correct
53 Correct 1272 ms 185812 KB Output is correct
54 Correct 1060 ms 199440 KB Output is correct
55 Correct 920 ms 183500 KB Output is correct
56 Correct 1170 ms 211644 KB Output is correct
57 Correct 936 ms 184024 KB Output is correct
58 Correct 1008 ms 184564 KB Output is correct
59 Correct 900 ms 210188 KB Output is correct