oj.uz

Submission #1018629

# Submission time Handle Problem Language Result Execution time Memory
1018629 2024-07-10T07:41:43 Z amirhoseinfar1385 Horses (IOI15_horses) C++17
57 / 100
 1500 ms 98436 KB 
#include "horses.h"
#include<bits/stdc++.h>
using namespace std;
const int maxn=500000+10,mod=1e9+7,lg=20,kaf=(1<<(lg));
int allx[maxn],ally[maxn],n;
set<int>st;
struct segment{
	struct node{
		long long maxa,zarb;
		node(){
			maxa=0;
			zarb=1;
		}
	};
	node seg[(1<<(lg+1))];
	void upd(int i,int w){
		i+=kaf;
		seg[i].zarb=seg[i].maxa=w;
		i>>=1;
		while(i>0){
			seg[i].maxa=max(seg[(i<<1)].maxa,seg[(i<<1)^1].maxa);
			seg[i].zarb=seg[(i<<1)].zarb*seg[(i<<1)^1].zarb%mod;
			i>>=1;
		}
	}
	long long porszarb(int i,int l,int r,int tl,int tr){
		if(l>r||l>tr||r<tl||tl>tr){
			return 1;
		}
		if(l>=tl&&r<=tr){
			return seg[i].zarb;
		}
		int m=(l+r)>>1;
		return porszarb((i<<1),l,m,tl,tr)*porszarb((i<<1)^1,m+1,r,tl,tr)%mod;
	}
	long long porsmx(int i,int l,int r,int tl,int tr){
		if(l>r||l>tr||r<tl||tl>tr){
			return 0;
		}
		if(l>=tl&&r<=tr){
			return seg[i].maxa;
		}
		int m=(l+r)>>1;
		return max(porsmx((i<<1),l,m,tl,tr),porsmx((i<<1)^1,m+1,r,tl,tr));
	}
}segx,segy;
int calc(){
	long long low=0;
	long long unnow=1;
	vector<int>ind;
	while((int)st.size()>0){
		unnow*=allx[(*st.rbegin())];
		ind.push_back((*st.rbegin()));
		st.erase((*st.rbegin()));
		if(unnow>1000000000){
			break;
		}
	}
	unnow/=allx[ind.back()];
	long long mx=0;
	for(int i=0;i<(int)ind.size();i++){
		mx=max(mx,unnow*segy.porsmx(1,0,kaf-1,ind[i],n));
		unnow/=allx[ind[i]];
	}
	mx%=mod;
	mx*=segx.porszarb(1,0,kaf-1,0,ind.back());
	mx%=mod;
	for(auto x:ind){
		st.insert(x);
	}
	return mx;
}

int init(int N, int X[], int Y[]) {
	n=N;
	allx[0]=1;
	st.insert(0);
	for(int i=1;i<=n;i++){
		//cout<<i<<endl;
		allx[i]=X[i-1];
		segx.upd(i,allx[i]);
		ally[i]=Y[i-1];
		segy.upd(i,ally[i]);
		if(allx[i]>1){
			st.insert(i);
		}
	}
	return calc();
}

int updateX(int pos, int val) {
	pos++;	
	allx[pos]=val;
	if(allx[pos]==1){
		st.erase(pos);
	}else{
		st.insert(pos);
	}
	segx.upd(pos,val);
	return calc();
}

int updateY(int pos, int val) {
	pos++;
	ally[pos]=val;
	segy.upd(pos,val);
	return calc();
}

Compilation message

horses.cpp: In function 'int calc()':
horses.cpp:71:9: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   71 |  return mx;
      |         ^~
horses.cpp:48:12: warning: unused variable 'low' [-Wunused-variable]
   48 |  long long low=0;
      |            ^~~

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 66136 KB Output is correct
2 Correct 16 ms 66136 KB Output is correct
3 Correct 12 ms 66140 KB Output is correct
4 Correct 13 ms 66140 KB Output is correct
5 Correct 18 ms 66140 KB Output is correct
6 Correct 13 ms 66140 KB Output is correct
7 Correct 13 ms 66140 KB Output is correct
8 Correct 15 ms 66056 KB Output is correct
9 Correct 14 ms 66152 KB Output is correct
10 Correct 13 ms 66140 KB Output is correct
11 Correct 13 ms 66108 KB Output is correct
12 Correct 17 ms 66216 KB Output is correct
13 Correct 13 ms 66140 KB Output is correct
14 Correct 13 ms 66200 KB Output is correct
15 Correct 13 ms 66136 KB Output is correct
16 Correct 13 ms 66140 KB Output is correct
17 Correct 13 ms 66140 KB Output is correct
18 Correct 13 ms 66192 KB Output is correct
19 Correct 13 ms 66140 KB Output is correct
20 Correct 14 ms 66264 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 66140 KB Output is correct
2 Correct 13 ms 66256 KB Output is correct
3 Correct 13 ms 66140 KB Output is correct
4 Correct 13 ms 66140 KB Output is correct
5 Correct 13 ms 66264 KB Output is correct
6 Correct 12 ms 66140 KB Output is correct
7 Correct 17 ms 66140 KB Output is correct
8 Correct 16 ms 66140 KB Output is correct
9 Correct 13 ms 66140 KB Output is correct
10 Correct 12 ms 66292 KB Output is correct
11 Correct 13 ms 66140 KB Output is correct
12 Correct 16 ms 66136 KB Output is correct
13 Correct 13 ms 66140 KB Output is correct
14 Correct 13 ms 66280 KB Output is correct
15 Correct 14 ms 66140 KB Output is correct
16 Correct 14 ms 66140 KB Output is correct
17 Correct 12 ms 66256 KB Output is correct
18 Correct 12 ms 66140 KB Output is correct
19 Correct 13 ms 66140 KB Output is correct
20 Correct 12 ms 66140 KB Output is correct
21 Correct 13 ms 66140 KB Output is correct
22 Correct 12 ms 66140 KB Output is correct
23 Correct 15 ms 66136 KB Output is correct
24 Correct 14 ms 66248 KB Output is correct
25 Correct 23 ms 66136 KB Output is correct
26 Correct 16 ms 66140 KB Output is correct
27 Correct 19 ms 66136 KB Output is correct
28 Correct 21 ms 66124 KB Output is correct
29 Correct 18 ms 66140 KB Output is correct
30 Correct 14 ms 66276 KB Output is correct
31 Correct 17 ms 66136 KB Output is correct
32 Correct 18 ms 66300 KB Output is correct

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1542 ms 98436 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 66136 KB Output is correct
2 Correct 12 ms 66136 KB Output is correct
3 Correct 12 ms 66224 KB Output is correct
4 Correct 13 ms 66140 KB Output is correct
5 Correct 14 ms 66216 KB Output is correct
6 Correct 12 ms 66140 KB Output is correct
7 Correct 12 ms 66140 KB Output is correct
8 Correct 16 ms 66136 KB Output is correct
9 Correct 12 ms 66136 KB Output is correct
10 Correct 13 ms 66132 KB Output is correct
11 Correct 12 ms 66196 KB Output is correct
12 Correct 12 ms 66140 KB Output is correct
13 Correct 12 ms 66140 KB Output is correct
14 Correct 12 ms 66140 KB Output is correct
15 Correct 15 ms 66136 KB Output is correct
16 Correct 12 ms 66140 KB Output is correct
17 Correct 13 ms 66256 KB Output is correct
18 Correct 14 ms 66140 KB Output is correct
19 Correct 15 ms 66196 KB Output is correct
20 Correct 15 ms 66136 KB Output is correct
21 Correct 12 ms 66288 KB Output is correct
22 Correct 12 ms 66136 KB Output is correct
23 Correct 13 ms 66280 KB Output is correct
24 Correct 15 ms 66172 KB Output is correct
25 Correct 16 ms 66140 KB Output is correct
26 Correct 15 ms 66140 KB Output is correct
27 Correct 19 ms 66140 KB Output is correct
28 Correct 15 ms 66140 KB Output is correct
29 Correct 13 ms 66140 KB Output is correct
30 Correct 13 ms 66356 KB Output is correct
31 Correct 17 ms 66140 KB Output is correct
32 Correct 20 ms 66140 KB Output is correct
33 Correct 149 ms 73996 KB Output is correct
34 Correct 143 ms 73960 KB Output is correct
35 Correct 286 ms 97360 KB Output is correct
36 Correct 265 ms 97360 KB Output is correct
37 Correct 185 ms 74060 KB Output is correct
38 Correct 223 ms 86080 KB Output is correct
39 Correct 134 ms 73812 KB Output is correct
40 Correct 242 ms 97348 KB Output is correct
41 Correct 166 ms 73808 KB Output is correct
42 Correct 171 ms 73812 KB Output is correct
43 Correct 243 ms 97616 KB Output is correct
44 Correct 237 ms 97360 KB Output is correct

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 66140 KB Output is correct
2 Correct 13 ms 66048 KB Output is correct
3 Correct 13 ms 66140 KB Output is correct
4 Correct 13 ms 66288 KB Output is correct
5 Correct 13 ms 66136 KB Output is correct
6 Correct 13 ms 66392 KB Output is correct
7 Correct 14 ms 66040 KB Output is correct
8 Correct 12 ms 66136 KB Output is correct
9 Correct 12 ms 66136 KB Output is correct
10 Correct 12 ms 66140 KB Output is correct
11 Correct 12 ms 66280 KB Output is correct
12 Correct 12 ms 66140 KB Output is correct
13 Correct 12 ms 66136 KB Output is correct
14 Correct 12 ms 66136 KB Output is correct
15 Correct 12 ms 66136 KB Output is correct
16 Correct 12 ms 66136 KB Output is correct
17 Correct 12 ms 66288 KB Output is correct
18 Correct 12 ms 66136 KB Output is correct
19 Correct 12 ms 66136 KB Output is correct
20 Correct 12 ms 66140 KB Output is correct
21 Correct 12 ms 66140 KB Output is correct
22 Correct 13 ms 66140 KB Output is correct
23 Correct 13 ms 66140 KB Output is correct
24 Correct 12 ms 66140 KB Output is correct
25 Correct 14 ms 66140 KB Output is correct
26 Correct 13 ms 66140 KB Output is correct
27 Correct 18 ms 66140 KB Output is correct
28 Correct 16 ms 66296 KB Output is correct
29 Correct 16 ms 66140 KB Output is correct
30 Correct 13 ms 66264 KB Output is correct
31 Correct 15 ms 66136 KB Output is correct
32 Correct 17 ms 66304 KB Output is correct
33 Execution timed out 1555 ms 98384 KB Time limit exceeded
34 Halted 0 ms 0 KB -