oj.uz

Submission #1090558

# Submission time Handle Problem Language Result Execution time Memory
1090558 2024-09-18T12:48:19 Z owoovo Horses (IOI15_horses) C++17
37 / 100
 540 ms 48720 KB 
#include "horses.h"
#include<bits/stdc++.h>
#define ll long long
#define ld double
#define F first 
#define S second
#define lc id*2+1
#define rc id*2+2
using namespace std;
const ll p=1e9+7;
ll pw(ll a,ll b){
	ll ans=1;
	while(b){
		if(b&1)ans*=a,ans%=p;
		b>>=1,a*=a,a%=p;
	}
	return ans;
}
ll x[500010],y[500010],n;
struct BIT{
	ll ori[500010];
	void init(){
		for(int i=0;i<=n;i++)ori[i]=1;
		return;
	}
	void modify(ll x,int pos){
		while(pos<=n){
			ori[pos]*=x;
			ori[pos]%=p;
			pos+=pos&(-pos);
		}
		return;
	}
	ll query(ll pos){
		ll ans=1;
		while(pos){
			ans*=ori[pos];
			ans%=p;
			pos-=pos&(-pos);
		}
		return ans;
	}
}bit;
struct SEG_TREE{
	pair<int,int> ori[2000010];
	void build(int l,int r,int id){
		if(l==r){
			ori[id]={y[l],l};
			return;
		}
		int m=(l+r)>>1;
		build(l,m,lc);
		build(m+1,r,rc);
		ori[id]=max(ori[lc],ori[rc]);
		return;
	}
	void modify(int l,int r,int pos,int id,int x){
		if(l==pos&&r==pos){
			ori[id]={x,l};
			return;
		}
		int m=(l+r)>>1;
		if(pos<=m){
			modify(l,m,pos,lc,x);
		}else{
			modify(m+1,r,pos,rc,x);
		}
		ori[id]=max(ori[lc],ori[rc]);
		return;
	}
	pair<int,int> query(int l,int r,int ql,int qr,int id){
		if(l==ql&&r==qr){
			return ori[id];
		}
		int m=(l+r)>>1;
		if(qr<=m){
			return query(l,m,ql,qr,lc);
		}else if(m<ql){
			return query(m+1,r,ql,qr,rc);
		}else{
			return max(query(l,m,ql,m,lc),query(m+1,r,m+1,qr,rc));
		}
	}
}seg;

set<int> big;

ll q(){
	if(big.size()==1){
		return seg.query(1,n,1,n,0).F;
	}
	set<int>::iterator k=(--(--big.end()));
	ll pos=0;
	int now=0;
	ld nw=0,maxn=0;
	while(now<50&&k!=big.begin()){
		assert(x[*k]>1);
		now++;
		k--;
	}
	while(k!=(--big.end())){
		nw+=log2(x[*k]);
		//cout<<*k<<" "<<*(nx)<<"\n";
		pair<int,int> pp=seg.query(1,n,*k,n,0);
		//cout<<pp.F<<" "<<pp.S<<"\n";
		if(maxn<nw+log2(pp.F)){
			maxn=nw+log2(pp.F);
			pos=pp.S;
		}
		++k;
	}
	ll a=bit.query(pos);
	//cout<<a<<"?\n";
	a*=y[pos];
	//cout<<a<<" 888\n";
	a%=p;
	//cout<<pos<<"\n";
	return a;
}

int init(int N, int X[], int Y[]) {
	n=N;
	big.insert(n+1);
	bit.init();
	for(int i=0;i<n;i++){
		x[i+1]=X[i];
		bit.modify(x[i+1],i+1);
		if(x[i+1]>1)big.insert(i+1);
		y[i+1]=Y[i];
	}
	seg.build(1,n,0);
	return q();
}

int updateX(int pos, int val) {	
	pos+=1;
	bit.modify((pw(x[pos],p-2)*val)%p,pos);
	x[pos]=val;
	if(val==1)big.erase(pos);
	else big.insert(pos);
	return q();
}

int updateY(int pos, int val) {
	pos+=1;
	seg.modify(1,n,pos,0,val);
	y[pos]=val;
	return q();
}

Compilation message

horses.cpp: In member function 'void BIT::modify(long long int, int)':
horses.cpp:26:17: warning: declaration of 'x' shadows a global declaration [-Wshadow]
   26 |  void modify(ll x,int pos){
      |                 ^
horses.cpp:19:4: note: shadowed declaration is here
   19 | ll x[500010],y[500010],n;
      |    ^
horses.cpp: In member function 'void SEG_TREE::modify(int, int, int, int, int)':
horses.cpp:57:45: warning: declaration of 'x' shadows a global declaration [-Wshadow]
   57 |  void modify(int l,int r,int pos,int id,int x){
      |                                         ~~~~^
horses.cpp:19:4: note: shadowed declaration is here
   19 | ll x[500010],y[500010],n;
      |    ^
horses.cpp: In function 'long long int q()':
horses.cpp:90:22: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   90 |   return seg.query(1,n,1,n,0).F;
      |                      ^
horses.cpp:90:26: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   90 |   return seg.query(1,n,1,n,0).F;
      |                          ^
horses.cpp:104:32: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  104 |   pair<int,int> pp=seg.query(1,n,*k,n,0);
      |                                ^
horses.cpp:104:37: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  104 |   pair<int,int> pp=seg.query(1,n,*k,n,0);
      |                                     ^
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:123:14: warning: conversion from 'long long int' to 'std::set<int>::value_type' {aka 'int'} may change value [-Wconversion]
  123 |  big.insert(n+1);
      |             ~^~
horses.cpp:131:14: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  131 |  seg.build(1,n,0);
      |              ^
horses.cpp:132:10: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  132 |  return q();
      |         ~^~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:141:10: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  141 |  return q();
      |         ~^~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:146:15: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  146 |  seg.modify(1,n,pos,0,val);
      |               ^
horses.cpp:148:10: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  148 |  return q();
      |         ~^~

Subtask #1
17.0 / 17.0

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

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 344 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 1 ms 348 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 0 ms 348 KB Output is correct
23 Correct 3 ms 348 KB Output is correct
24 Correct 3 ms 348 KB Output is correct
25 Correct 3 ms 344 KB Output is correct
26 Correct 3 ms 344 KB Output is correct
27 Incorrect 2 ms 348 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 395 ms 48576 KB Output is correct
2 Correct 488 ms 48696 KB Output is correct
3 Correct 483 ms 48720 KB Output is correct
4 Correct 540 ms 48592 KB Output is correct

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 344 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 0 ms 348 KB Output is correct
23 Correct 3 ms 524 KB Output is correct
24 Correct 3 ms 600 KB Output is correct
25 Correct 3 ms 348 KB Output is correct
26 Correct 3 ms 348 KB Output is correct
27 Incorrect 2 ms 348 KB Output isn't correct
28 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 1 ms 504 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 1 ms 348 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 0 ms 348 KB Output is correct
23 Correct 3 ms 348 KB Output is correct
24 Correct 3 ms 600 KB Output is correct
25 Correct 3 ms 348 KB Output is correct
26 Correct 3 ms 348 KB Output is correct
27 Incorrect 2 ms 348 KB Output isn't correct
28 Halted 0 ms 0 KB -