oj.uz

Submission #620854

# Submission time Handle Problem Language Result Execution time Memory
620854 2022-08-03T09:46:55 Z Hazem Horses (IOI15_horses) C++14
37 / 100
 672 ms 56976 KB 
#include <bits/stdc++.h>
#define LL long long
#define F first
#define S second

using namespace std;

const int M = 5e5+10;
const int MOD = 1e9+7;

LL add(LL a,LL b){
	return (a+b)%MOD;
}

LL mult(LL a,LL b){
	return (a*b)%MOD;
}

LL fastpow(LL n,LL k){

	LL ret = 1;

	while(k){

		if(k&1)ret = mult(ret,n);
		k /= 2;
		n = mult(n,n);
	}
	return ret;
}

LL divide(LL a,LL b){
	return mult(a,fastpow(b,MOD-2));
}

LL a[M],b[M],tree[M*4][2],n;
LL pr = 1;
set<int>st;

void update(int v,int tl,int tr,int pos,int val,int t){

	if(tl==tr){
		tree[v][t] = val;
		return ;
	}

	int mid = (tl+tr)/2;
	if(pos<=mid)
		update(v*2,tl,mid,pos,val,t);
	else 
		update(v*2+1,mid+1,tr,pos,val,t);

	if(!t)
		tree[v][t] = max(tree[v*2][t],tree[v*2+1][t]);
	else 
		tree[v][t] = mult(tree[v*2][t],tree[v*2+1][t]);
}

LL get(int v,int tl,int tr,int l,int r,int t){

	if(tl>r||tr<l)
		return 1;

	if(tl>=l&&tr<=r)
		return tree[v][t];

	int mid = (tl+tr)/2;
	if(!t)
		return max(get(v*2,tl,mid,l,r,t),get(v*2+1,mid+1,tr,l,r,t));
	else 
		return mult(get(v*2,tl,mid,l,r,t),get(v*2+1,mid+1,tr,l,r,t));
}

LL calc(){

	vector<pair<LL,LL>>vec;
	int cnt = 0;
	int last = n+1;
	for(auto it:st){
		if(cnt==30)
			break;
		
		cnt++;
		int idx = -(it);
		if(last-idx>1)
			vec.push_back({1,get(1,1,n,idx+1,last-1,0)});
		
		last = idx;
		vec.push_back({a[idx],b[idx]});
	}
	pr = (last==1)?1:get(1,1,n,1,last-1,1);

	if(vec.empty())
		vec.push_back({1,get(1,1,n,1,n,0)});
	
	reverse(vec.begin(),vec.end());
	LL idx = 0,cur = 1;
	for(int i = 1;i<vec.size();i++){
		
		if((cur*vec[i].F>vec[idx].S)||(cur*vec[i].F*vec[i].S>vec[idx].S))
			idx = i,cur = 1;
		else 
			cur *= vec[i].F;
	}

	cur = 1;
	for(int i=0;i<=idx;i++)
		cur = mult(cur,vec[i].F);
	
	return mult(pr,mult(cur,vec[idx].S));
}

int init(int N, int X[], int Y[]) {
	
	n = N;
	a[0] = 1;
	for(int i=1;i<=n;i++){
		a[i] = X[i-1];
		b[i] = Y[i-1];
		update(1,1,n,i,b[i],0);
		update(1,1,n,i,a[i],1);

		if(a[i]>1)
			st.insert(-i);
	}

	return calc();
}

int updateX(int pos, int val) {	

	if(a[pos+1]>1)
		st.erase(-pos-1);

	a[pos+1] = val;
	update(1,1,n,pos+1,val,1);
	if(a[pos+1]>1)
		st.insert(-pos-1);

	return calc();
}

int updateY(int pos, int val) {
	
	b[pos+1] = val;
	update(1,1,n,pos+1,b[pos+1],0);

	return calc();
}

Compilation message

horses.cpp: In function 'long long int calc()':
horses.cpp:78:14: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   78 |  int last = n+1;
      |             ~^~
horses.cpp:86:29: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   86 |    vec.push_back({1,get(1,1,n,idx+1,last-1,0)});
      |                             ^
horses.cpp:91:27: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   91 |  pr = (last==1)?1:get(1,1,n,1,last-1,1);
      |                           ^
horses.cpp:94:28: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   94 |   vec.push_back({1,get(1,1,n,1,n,0)});
      |                            ^
horses.cpp:94:32: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   94 |   vec.push_back({1,get(1,1,n,1,n,0)});
      |                                ^
horses.cpp:98:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   98 |  for(int i = 1;i<vec.size();i++){
      |                ~^~~~~~~~~~~
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:120:14: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  120 |   update(1,1,n,i,b[i],0);
      |              ^
horses.cpp:120:21: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  120 |   update(1,1,n,i,b[i],0);
      |                  ~~~^
horses.cpp:121:14: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  121 |   update(1,1,n,i,a[i],1);
      |              ^
horses.cpp:121:21: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  121 |   update(1,1,n,i,a[i],1);
      |                  ~~~^
horses.cpp:127:13: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  127 |  return calc();
      |         ~~~~^~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:136:13: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  136 |  update(1,1,n,pos+1,val,1);
      |             ^
horses.cpp:140:13: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  140 |  return calc();
      |         ~~~~^~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:146:13: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  146 |  update(1,1,n,pos+1,b[pos+1],0);
      |             ^
horses.cpp:146:28: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  146 |  update(1,1,n,pos+1,b[pos+1],0);
      |                     ~~~~~~~^
horses.cpp:148:13: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  148 |  return calc();
      |         ~~~~^~

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 1 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 1 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 1 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 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 0 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 1 ms 260 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 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 1 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 Correct 1 ms 212 KB Output is correct
22 Correct 0 ms 212 KB Output is correct
23 Correct 4 ms 340 KB Output is correct
24 Correct 3 ms 340 KB Output is correct
25 Correct 2 ms 340 KB Output is correct
26 Correct 2 ms 340 KB Output is correct
27 Incorrect 4 ms 340 KB Output isn't correct
28 Halted 0 ms 0 KB -

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 396 ms 52912 KB Output is correct
2 Correct 596 ms 52832 KB Output is correct
3 Correct 540 ms 56516 KB Output is correct
4 Correct 672 ms 56976 KB Output is correct

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 1 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 1 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 1 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 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 0 ms 212 KB Output is correct
23 Correct 7 ms 340 KB Output is correct
24 Correct 2 ms 340 KB Output is correct
25 Correct 3 ms 340 KB Output is correct
26 Correct 2 ms 340 KB Output is correct
27 Incorrect 3 ms 340 KB Output isn't correct
28 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 1 ms 212 KB Output is correct
5 Correct 1 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 1 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 292 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 0 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 292 KB Output is correct
18 Correct 1 ms 212 KB Output is correct
19 Correct 1 ms 216 KB Output is correct
20 Correct 0 ms 212 KB Output is correct
21 Correct 0 ms 212 KB Output is correct
22 Correct 0 ms 212 KB Output is correct
23 Correct 5 ms 340 KB Output is correct
24 Correct 4 ms 340 KB Output is correct
25 Correct 2 ms 340 KB Output is correct
26 Correct 2 ms 340 KB Output is correct
27 Incorrect 5 ms 340 KB Output isn't correct
28 Halted 0 ms 0 KB -