oj.uz

Submission #1018636

# Submission time Handle Problem Language Result Execution time Memory
1018636 2024-07-10T07:44:19 Z amirhoseinfar1385 Horses (IOI15_horses) C++17
57 / 100
 1500 ms 49084 KB 
#include "horses.h"
#include<bits/stdc++.h>
using namespace std;
const int maxn=500000+10,mod=1e9+7,lg=19,kaf=(1<<(lg));
int allx[maxn],ally[maxn],n;
set<int>st;
struct segment{
	struct node{
		int 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=1ll*seg[(i<<1)].zarb*seg[(i<<1)^1].zarb%mod;
			i>>=1;
		}
	}
	int 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 1ll*porszarb((i<<1),l,m,tl,tr)*porszarb((i<<1)^1,m+1,r,tl,tr)%mod;
	}
	int 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 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 member function 'void segment::upd(int, int)':
horses.cpp:22:55: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   22 |    seg[i].zarb=1ll*seg[(i<<1)].zarb*seg[(i<<1)^1].zarb%mod;
      |                ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~
horses.cpp: In member function 'int segment::porszarb(int, int, int, int, int)':
horses.cpp:34:71: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   34 |   return 1ll*porszarb((i<<1),l,m,tl,tr)*porszarb((i<<1)^1,m+1,r,tl,tr)%mod;
      |          ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~
horses.cpp: In function 'int calc()':
horses.cpp:70:9: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   70 |  return mx;
      |         ^~

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 16988 KB Output is correct
2 Correct 5 ms 16912 KB Output is correct
3 Correct 6 ms 17036 KB Output is correct
4 Correct 6 ms 16984 KB Output is correct
5 Correct 5 ms 16988 KB Output is correct
6 Correct 6 ms 16988 KB Output is correct
7 Correct 5 ms 16984 KB Output is correct
8 Correct 5 ms 16988 KB Output is correct
9 Correct 6 ms 16988 KB Output is correct
10 Correct 5 ms 16984 KB Output is correct
11 Correct 5 ms 16880 KB Output is correct
12 Correct 5 ms 16948 KB Output is correct
13 Correct 5 ms 16984 KB Output is correct
14 Correct 5 ms 16940 KB Output is correct
15 Correct 5 ms 16988 KB Output is correct
16 Correct 6 ms 16988 KB Output is correct
17 Correct 6 ms 16988 KB Output is correct
18 Correct 6 ms 16988 KB Output is correct
19 Correct 5 ms 16988 KB Output is correct
20 Correct 6 ms 16988 KB Output is correct

Subtask #2
17.0 / 17.0

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

Subtask #3
0 / 20.0

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

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 16984 KB Output is correct
2 Correct 5 ms 16988 KB Output is correct
3 Correct 5 ms 17032 KB Output is correct
4 Correct 9 ms 16984 KB Output is correct
5 Correct 6 ms 16988 KB Output is correct
6 Correct 6 ms 16988 KB Output is correct
7 Correct 7 ms 16988 KB Output is correct
8 Correct 6 ms 16984 KB Output is correct
9 Correct 6 ms 16984 KB Output is correct
10 Correct 5 ms 16988 KB Output is correct
11 Correct 5 ms 16988 KB Output is correct
12 Correct 7 ms 16936 KB Output is correct
13 Correct 5 ms 16988 KB Output is correct
14 Correct 6 ms 16988 KB Output is correct
15 Correct 5 ms 16988 KB Output is correct
16 Correct 5 ms 16968 KB Output is correct
17 Correct 6 ms 16900 KB Output is correct
18 Correct 6 ms 16988 KB Output is correct
19 Correct 5 ms 16984 KB Output is correct
20 Correct 5 ms 16988 KB Output is correct
21 Correct 5 ms 16988 KB Output is correct
22 Correct 6 ms 16988 KB Output is correct
23 Correct 7 ms 16988 KB Output is correct
24 Correct 6 ms 17060 KB Output is correct
25 Correct 7 ms 16928 KB Output is correct
26 Correct 7 ms 17008 KB Output is correct
27 Correct 10 ms 16988 KB Output is correct
28 Correct 9 ms 17076 KB Output is correct
29 Correct 7 ms 16988 KB Output is correct
30 Correct 7 ms 16988 KB Output is correct
31 Correct 9 ms 17040 KB Output is correct
32 Correct 11 ms 16900 KB Output is correct
33 Correct 148 ms 24736 KB Output is correct
34 Correct 145 ms 24732 KB Output is correct
35 Correct 289 ms 48260 KB Output is correct
36 Correct 269 ms 48208 KB Output is correct
37 Correct 190 ms 24656 KB Output is correct
38 Correct 242 ms 36648 KB Output is correct
39 Correct 139 ms 24660 KB Output is correct
40 Correct 249 ms 48208 KB Output is correct
41 Correct 160 ms 24712 KB Output is correct
42 Correct 180 ms 24660 KB Output is correct
43 Correct 241 ms 48004 KB Output is correct
44 Correct 237 ms 47956 KB Output is correct

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 16988 KB Output is correct
2 Correct 5 ms 16988 KB Output is correct
3 Correct 6 ms 16988 KB Output is correct
4 Correct 7 ms 16956 KB Output is correct
5 Correct 6 ms 16820 KB Output is correct
6 Correct 6 ms 16984 KB Output is correct
7 Correct 6 ms 16988 KB Output is correct
8 Correct 5 ms 16996 KB Output is correct
9 Correct 5 ms 16988 KB Output is correct
10 Correct 6 ms 16944 KB Output is correct
11 Correct 7 ms 16728 KB Output is correct
12 Correct 7 ms 16732 KB Output is correct
13 Correct 7 ms 16732 KB Output is correct
14 Correct 6 ms 16732 KB Output is correct
15 Correct 6 ms 16736 KB Output is correct
16 Correct 6 ms 16732 KB Output is correct
17 Correct 6 ms 16820 KB Output is correct
18 Correct 6 ms 16732 KB Output is correct
19 Correct 6 ms 16732 KB Output is correct
20 Correct 5 ms 16876 KB Output is correct
21 Correct 6 ms 16732 KB Output is correct
22 Correct 6 ms 16868 KB Output is correct
23 Correct 7 ms 16732 KB Output is correct
24 Correct 7 ms 16732 KB Output is correct
25 Correct 14 ms 16732 KB Output is correct
26 Correct 7 ms 16728 KB Output is correct
27 Correct 19 ms 16728 KB Output is correct
28 Correct 8 ms 16732 KB Output is correct
29 Correct 8 ms 16776 KB Output is correct
30 Correct 10 ms 16984 KB Output is correct
31 Correct 12 ms 16880 KB Output is correct
32 Correct 13 ms 16984 KB Output is correct
33 Execution timed out 1577 ms 48916 KB Time limit exceeded
34 Halted 0 ms 0 KB -