oj.uz

Submission #343565

# Submission time Handle Problem Language Result Execution time Memory
343565 2021-01-04T08:41:45 Z NhatMinh0208 Horses (IOI15_horses) C++14
100 / 100
 732 ms 42860 KB 
/*
	Normie's Template v2.0
*/
 
// Standard library in one include.
#include <bits/stdc++.h>
using namespace std;
 
// ordered_set library.
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define ordered_set(el) tree<el,null_type,less<el>,rb_tree_tag,tree_order_statistics_node_update>
 
// AtCoder library. (Comment out these two lines if you're not submitting in AtCoder.) (Or if you want to use it in other judges, run expander.py first.)
//#include <atcoder/all>
//using namespace atcoder;
 
//Pragmas (Comment out these three lines if you're submitting in szkopul.)
#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
 
//File I/O.
#define FILE_IN "cseq.inp"
#define FILE_OUT "cseq.out"
#define ofile freopen(FILE_IN,"r",stdin);freopen(FILE_OUT,"w",stdout)
 
//Fast I/O.
#define fio ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define nfio cin.tie(0);cout.tie(0)
#define endl "\n"
 
//Order checking.
#define ord(a,b,c) ((a>=b)and(b>=c))
 
//min/max redefines, so i dont have to resolve annoying compile errors.
#define min(a,b) (((a)<(b))?(a):(b))
#define max(a,b) (((a)>(b))?(a):(b))
 
//Constants.
#define MOD (ll(1000000007))
#define MAX 300001
#define mag 320
 
//Pairs and 3-pairs.
#define p1 first
#define p2 second.first
#define p3 second.second
#define fi first
#define se second
#define pii(element_type) pair<element_type,element_type>
#define piii(element_type) pair<element_type,pii(element_type)>
 
//Quick power of 2.
#define pow2(x) (ll(1)<<x)
 
//Short for-loops.
#define ff(i,__,___) for(int i=__;i<=___;i++)
#define rr(i,__,___) for(int i=__;i>=___;i--)
 
//Typedefs.
#define bi BigInt
typedef long long ll;
typedef long double ld;
typedef short sh;
//---------END-------//
#include "horses.h"
int bow(int a, int x, int p)
{
	if (!x) return 1;
	ll res=bow(a,x/2,p);
	res*=res;
	res%=p;
	if (x%2)
	{
		res*=a;
		res%=p;
	}
	return res;
};
struct seg
{
	int val[2000001];
	void update(int l, int r, int cur, int x, int d)
	{
	//	cout<<"update "<<l<<' '<<r<<' '<<cur<<' '<<x<<' '<<d<<endl;
		if ((l<=x)and(x<=r))
		{
			if (l==r)
			{
				val[cur]=d;
			}
			else
			{
				int mid=(l+r)/2;
				update(l,mid,(cur<<1),x,d);
				update(mid+1,r,(cur<<1)+1,x,d);
				val[cur]=max(val[(cur<<1)],val[(cur<<1)+1]);
			}
		}
	}
	int get(int l, int r, int cur, int tl, int tr)
	{
	//	cout<<"update "<<l<<' '<<r<<' '<<cur<<' '<<tl<<' '<<tr<<endl;
		if ((tl>r)or(tr<l)) return 0;
		if ((tl<=l)and(tr>=r)) return val[cur];
		else
		{
			int mid=(l+r)/2;
			
			int a=get(l,mid,(cur<<1),tl,tr);
			int b=get(mid+1,r,(cur<<1)+1,tl,tr);
			return (max(a,b));
		}
	}
};
seg st;
int x[500001],y[500001];
int inv[500001];
int n,m,i,j,k,t,t1,u,v,a,b;
set<int,greater<int>> g1;
ll co=1;
ll maxx=1,modd;
ll cur,left;
ll ask()
{
//	cout<<"value of co:"<<co<<endl;
//	cout<<"---------arrray-----------"<<endl;
//	for (int i=0;i<n;i++) cout<<x[i]<<' '<<y[i]<<endl;
//	cout<<"--------------------------"<<endl;
	cur=co;
	maxx=0;
	modd=0;
	for (int g : g1)
	{
		u=st.get(0,n-1,1,g,n-1);
//		cout<<g<<' '<<maxx<<' '<<modd<<' '<<u<<' '<<cur<<endl;
		if (maxx<u)
		{
			maxx=u;
			modd=ll(u)*cur;
			modd%=MOD;
		}
		if (g==-1) break;
		maxx*=x[g];
		if (maxx>1e9) break;
		cur*=inv[g];
		cur%=MOD;
	}
	return modd;
}
int init(int N, int X[], int Y[]) {
	n=N;
	for (i=0;i<N;i++)
	{
		x[i]=X[i];
		y[i]=Y[i];
		st.update(0,n-1,1,i,Y[i]);
		if (X[i]>1) g1.insert(i);
		co*=X[i];
		co%=MOD;
		inv[i]=bow(x[i],MOD-2,MOD);
	}
	g1.insert(-1);
	return ask();
}
int updateX(int pos, int val) {	
	co*=bow(x[pos],MOD-2,MOD);
	co%=MOD;
	co*=val;
	co%=MOD;
	if (x[pos]>1) g1.erase(pos);
	x[pos]=val;
	inv[pos]=bow(x[pos],MOD-2,MOD);
	if (x[pos]>1) g1.insert(pos);
	return ask();
}
int updateY(int pos, int val) {
	st.update(0,n-1,1,pos,val);
	return ask();
}

Compilation message

horses.cpp:20: warning: ignoring #pragma comment  [-Wunknown-pragmas]
   20 | #pragma comment(linker, "/stack:200000000")
      | 
horses.cpp: In function 'int bow(int, int, int)':
horses.cpp:80:9: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   80 |  return res;
      |         ^~~
horses.cpp: In function 'll ask()':
horses.cpp:147:7: warning: conversion from 'll' {aka 'long long int'} to 'double' may change value [-Wconversion]
  147 |   if (maxx>1e9) break;
      |       ^~~~
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:166:12: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  166 |  return ask();
      |         ~~~^~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:177:12: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  177 |  return ask();
      |         ~~~^~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:181:12: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  181 |  return ask();
      |         ~~~^~

Subtask #1
17.0 / 17.0

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

Subtask #2
17.0 / 17.0

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

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 729 ms 38764 KB Output is correct
2 Correct 660 ms 38840 KB Output is correct
3 Correct 617 ms 40552 KB Output is correct
4 Correct 695 ms 42404 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 0 ms 364 KB Output is correct
3 Correct 0 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 0 ms 364 KB Output is correct
12 Correct 1 ms 364 KB Output is correct
13 Correct 1 ms 364 KB Output is correct
14 Correct 1 ms 364 KB Output is correct
15 Correct 1 ms 364 KB Output is correct
16 Correct 1 ms 364 KB Output is correct
17 Correct 1 ms 364 KB Output is correct
18 Correct 0 ms 364 KB Output is correct
19 Correct 1 ms 364 KB Output is correct
20 Correct 1 ms 364 KB Output is correct
21 Correct 1 ms 364 KB Output is correct
22 Correct 1 ms 364 KB Output is correct
23 Correct 2 ms 364 KB Output is correct
24 Correct 2 ms 364 KB Output is correct
25 Correct 3 ms 492 KB Output is correct
26 Correct 2 ms 492 KB Output is correct
27 Correct 3 ms 364 KB Output is correct
28 Correct 3 ms 492 KB Output is correct
29 Correct 2 ms 364 KB Output is correct
30 Correct 3 ms 492 KB Output is correct
31 Correct 2 ms 364 KB Output is correct
32 Correct 3 ms 364 KB Output is correct
33 Correct 258 ms 14444 KB Output is correct
34 Correct 265 ms 14384 KB Output is correct
35 Correct 511 ms 37868 KB Output is correct
36 Correct 510 ms 37740 KB Output is correct
37 Correct 283 ms 14444 KB Output is correct
38 Correct 342 ms 26276 KB Output is correct
39 Correct 249 ms 14188 KB Output is correct
40 Correct 482 ms 37816 KB Output is correct
41 Correct 262 ms 14268 KB Output is correct
42 Correct 289 ms 14316 KB Output is correct
43 Correct 463 ms 37740 KB Output is correct
44 Correct 468 ms 37656 KB Output is correct

Subtask #5
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 0 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Correct 1 ms 364 KB Output is correct
13 Correct 1 ms 364 KB Output is correct
14 Correct 1 ms 364 KB Output is correct
15 Correct 1 ms 364 KB Output is correct
16 Correct 1 ms 364 KB Output is correct
17 Correct 1 ms 364 KB Output is correct
18 Correct 1 ms 364 KB Output is correct
19 Correct 1 ms 364 KB Output is correct
20 Correct 1 ms 364 KB Output is correct
21 Correct 1 ms 364 KB Output is correct
22 Correct 1 ms 364 KB Output is correct
23 Correct 2 ms 364 KB Output is correct
24 Correct 2 ms 364 KB Output is correct
25 Correct 3 ms 492 KB Output is correct
26 Correct 2 ms 492 KB Output is correct
27 Correct 3 ms 364 KB Output is correct
28 Correct 3 ms 492 KB Output is correct
29 Correct 2 ms 364 KB Output is correct
30 Correct 3 ms 492 KB Output is correct
31 Correct 2 ms 364 KB Output is correct
32 Correct 3 ms 364 KB Output is correct
33 Correct 732 ms 38764 KB Output is correct
34 Correct 662 ms 42860 KB Output is correct
35 Correct 615 ms 41324 KB Output is correct
36 Correct 694 ms 42860 KB Output is correct
37 Correct 262 ms 17152 KB Output is correct
38 Correct 259 ms 17004 KB Output is correct
39 Correct 499 ms 41836 KB Output is correct
40 Correct 488 ms 41944 KB Output is correct
41 Correct 285 ms 16080 KB Output is correct
42 Correct 345 ms 28524 KB Output is correct
43 Correct 249 ms 15852 KB Output is correct
44 Correct 484 ms 41708 KB Output is correct
45 Correct 262 ms 15980 KB Output is correct
46 Correct 276 ms 15852 KB Output is correct
47 Correct 466 ms 41664 KB Output is correct
48 Correct 464 ms 41836 KB Output is correct
49 Correct 372 ms 19940 KB Output is correct
50 Correct 353 ms 19820 KB Output is correct
51 Correct 623 ms 42732 KB Output is correct
52 Correct 566 ms 42732 KB Output is correct
53 Correct 707 ms 18940 KB Output is correct
54 Correct 498 ms 30828 KB Output is correct
55 Correct 361 ms 15980 KB Output is correct
56 Correct 597 ms 41580 KB Output is correct
57 Correct 491 ms 16876 KB Output is correct
58 Correct 630 ms 16844 KB Output is correct
59 Correct 462 ms 40556 KB Output is correct