oj.uz

Submission #669698

# Submission time Handle Problem Language Result Execution time Memory
669698 2022-12-07T05:46:05 Z alvingogo Horses (IOI15_horses) C++14
17 / 100
 507 ms 48320 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#define AquA cin.tie(0);ios_base::sync_with_stdio(0);
#define fs first
#define sc second
#define p_q priority_queue
using namespace std;

const int mod=1e9+7;
int mul(int x,int y){
	return 1ll*x%mod*y%mod;
}
struct ST{
	vector<pair<int,int> > st;
	void init(int n){
		st.resize(4*n);
	}
	void pull(int v){
		st[v].fs=mul(st[2*v+1].fs,st[2*v+2].fs);
		st[v].sc=max(st[2*v+1].sc,st[2*v+2].sc);
	}
	void update(int v,int L,int R,int p,int t,int x){
		if(L==R){
			if(t==1){
				st[v].fs=x;
			}
			else{
				st[v].sc=x;
			}
			return;
		}
		int m=(L+R)/2;
		if(p<=m){
			update(2*v+1,L,m,p,t,x);
		}
		else{
			update(2*v+2,m+1,R,p,t,x);
		}
		pull(v);
	}
	int q1(int v,int L,int R,int l,int r){
		if(r<l){
			return 1;
		}
		if(L==l && r==R){
			return st[v].fs;
		}
		int m=(L+R)/2;
		if(r<=m){
			return q1(2*v+1,L,m,l,r);
		}
		else if(l>m){
			return q1(2*v+2,m+1,R,l,r);
		}
		else{
			return mul(q1(2*v+1,L,m,l,m),q1(2*v+2,m+1,R,m+1,r));
		}
	}
	int q2(int v,int L,int R,int l,int r){
		if(L==l && r==R){
			return st[v].sc;
		}
		int m=(L+R)/2;
		if(r<=m){
			return q2(2*v+1,L,m,l,r);
		}
		else if(l>m){
			return q2(2*v+2,m+1,R,l,r);
		}
		else{
			return max(q2(2*v+1,L,m,l,m),q2(2*v+2,m+1,R,m+1,r));
		}
	}
}st;

set<pair<int,int> > s;
vector<int> x,y;
const long long inf=2e9;
int n;

int cal(){
	long long nw=1;
	int lst=n;
	for(auto h:s){
		nw=max(nw,(long long)st.q2(0,0,n-1,-h.fs,lst-1));
		nw*=h.sc;
		if(nw>=inf){
			return mul(nw,st.q1(0,0,n-1,0,-h.fs-1));
		}
		lst=-h.fs;
	}
	return nw%mod;
}
int init(int N,int X[],int Y[]){
	st.init(N);
	n=N;
	for(int i=0;i<n;i++){
		st.update(0,0,n-1,i,1,X[i]);
		x.push_back(X[i]);
		st.update(0,0,n-1,i,2,Y[i]);
		y.push_back(Y[i]);
		if(X[i]>=2 || i==0){
			s.insert({-i,X[i]});
		}
	}
	return cal();
}
int updateX(int pos,int val){
	st.update(0,0,n-1,pos,1,val);
	if(x[pos]>=2 || pos==0){
		s.erase({-pos,x[pos]});
	}
	x[pos]=val;
	if(x[pos]>=2 || pos==0){
		s.insert({-pos,x[pos]});
	}
	return cal();
}
int updateY(int pos,int val){
	st.update(0,0,n-1,pos,2,val);
	y[pos]=val;
	return cal();
}
/*

int main() {
	int n;
	cin >> n;
	int u[n]={0},v[n]={0};
	for(int i=0;i<n;i++){
		cin >> u[i];
	}
	for(int i=0;i<n;i++){
		cin >> v[i];
	}
	cout << init(n,u,v) << "\n";
	int q;
	cin >> q;
	while(q--){
		int t;
		cin >> t;
		int x,y;
		cin >> x >> y;
		if(t==1){
			cout << updateX(x,y) << "\n";		
		}
		else{
			cout << updateY(x,y) << "\n";
		}
	}
	return 0;
}
*/

Compilation message

horses.cpp: In function 'int mul(int, int)':
horses.cpp:11:20: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   11 |  return 1ll*x%mod*y%mod;
      |         ~~~~~~~~~~~^~~~
horses.cpp: In function 'int cal()':
horses.cpp:88:15: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   88 |    return mul(nw,st.q1(0,0,n-1,0,-h.fs-1));
      |               ^~
horses.cpp:92:11: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   92 |  return nw%mod;
      |         ~~^~~~

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 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 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 0 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
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 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 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 0 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 Incorrect 1 ms 212 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 507 ms 48320 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
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 0 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 1 ms 212 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 0 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 0 ms 212 KB Output is correct
21 Incorrect 0 ms 212 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #5
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 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 0 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 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 0 ms 212 KB Output is correct
19 Correct 0 ms 212 KB Output is correct
20 Correct 0 ms 212 KB Output is correct
21 Incorrect 0 ms 212 KB Output isn't correct
22 Halted 0 ms 0 KB -