oj.uz

Submission #1090490

# Submission time Handle Problem Language Result Execution time Memory
1090490 2024-09-18T12:07:03 Z owoovo Horses (IOI15_horses) C++17
17 / 100
 358 ms 76624 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 node{
	pair<ld,int> val;
	ld tag;
	node(){
	}
};
struct SEG_TREE{
	node ori[2000010];
	void pull(int l,int r,int id){
		if(l==r)return;
		ori[id].val=max(ori[lc].val,ori[rc].val);
		return;
	}
	void push(int l,int r,int id){
		ori[id].val.F+=ori[id].tag;
		if(l!=r){
			int m=(l+r)>>1;
			ori[lc].tag+=ori[id].tag;
			ori[rc].tag+=ori[id].tag;
		}
		ori[id].tag=0;
		return;
	}
	void build(int l,int r,int id){
		ori[id].val={0,l};
		ori[id].tag=0;
		if(l==r){
			return;
		}
		int m=(l+r)>>1;
		build(l,m,lc);
		build(m+1,r,rc);
		return;
	}
	void modify(int l,int r,int ml,int mr,int id,ld x){
		push(l,r,id);
		if(l==ml&&r==mr){
			ori[id].tag+=x;
			push(l,r,id);
			return;
		}
		int m=(l+r)>>1;
		if(mr<=m){
			modify(l,m,ml,mr,lc,x);
		}else if(m<ml){
			modify(m+1,r,ml,mr,rc,x);
		}else{
			modify(l,m,ml,m,lc,x);
			modify(m+1,r,m+1,mr,rc,x);
		}
		pull(l,r,id);
		return;
	}
	pair<ld,int> query(int l,int r,int ql,int qr,int id){
		push(l,r,id);
		if(l==ql&&r==qr){
			return ori[id].val;
		}
		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;

ll q(){
	pair<ld,int> ans=seg.query(1,n,1,n,0);
	ll a=bit.query(ans.S);
	a*=y[ans.S];
	a%=p;
	return a;
}



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

int updateX(int pos, int val) {	
	pos+=1;
	seg.modify(1,n,pos,n,0,log2(val)-log2(x[pos]));
	bit.modify(pw(x[pos],p-2),pos);
	bit.modify(val,pos);
	x[pos]=val;
	return q();
}

int updateY(int pos, int val) {
	pos+=1;
	seg.modify(1,n,pos,pos,0,log2(val)-log2(y[pos]));
	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::push(int, int, int)':
horses.cpp:60:8: warning: unused variable 'm' [-Wunused-variable]
   60 |    int m=(l+r)>>1;
      |        ^
horses.cpp: In member function 'void SEG_TREE::modify(int, int, int, int, int, double)':
horses.cpp:78:50: warning: declaration of 'x' shadows a global declaration [-Wshadow]
   78 |  void modify(int l,int r,int ml,int mr,int id,ld 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:114:31: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  114 |  pair<ld,int> ans=seg.query(1,n,1,n,0);
      |                               ^
horses.cpp:114:35: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  114 |  pair<ld,int> ans=seg.query(1,n,1,n,0);
      |                                   ^
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:130:14: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  130 |  seg.build(1,n,0);
      |              ^
horses.cpp:132:16: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  132 |   seg.modify(1,n,i,n,0,log2(x[i]));
      |                ^
horses.cpp:132:20: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  132 |   seg.modify(1,n,i,n,0,log2(x[i]));
      |                    ^
horses.cpp:133:16: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  133 |   seg.modify(1,n,i,i,0,log2(y[i]));
      |                ^
horses.cpp:136:10: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  136 |  return q();
      |         ~^~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:141:15: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  141 |  seg.modify(1,n,pos,n,0,log2(val)-log2(x[pos]));
      |               ^
horses.cpp:141:21: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  141 |  seg.modify(1,n,pos,n,0,log2(val)-log2(x[pos]));
      |                     ^
horses.cpp:145:10: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  145 |  return q();
      |         ~^~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:150:15: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  150 |  seg.modify(1,n,pos,pos,0,log2(val)-log2(y[pos]));
      |               ^
horses.cpp:152:10: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  152 |  return q();
      |         ~^~

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 47196 KB Output is correct
2 Correct 18 ms 47332 KB Output is correct
3 Correct 18 ms 47196 KB Output is correct
4 Correct 19 ms 47236 KB Output is correct
5 Correct 18 ms 47196 KB Output is correct
6 Correct 19 ms 47220 KB Output is correct
7 Correct 18 ms 47184 KB Output is correct
8 Correct 18 ms 47192 KB Output is correct
9 Correct 17 ms 47196 KB Output is correct
10 Correct 18 ms 47192 KB Output is correct
11 Correct 18 ms 47256 KB Output is correct
12 Correct 17 ms 47196 KB Output is correct
13 Correct 18 ms 47192 KB Output is correct
14 Correct 18 ms 47192 KB Output is correct
15 Correct 25 ms 47192 KB Output is correct
16 Correct 19 ms 47196 KB Output is correct
17 Correct 19 ms 47424 KB Output is correct
18 Correct 21 ms 47196 KB Output is correct
19 Correct 17 ms 47192 KB Output is correct
20 Correct 18 ms 47196 KB Output is correct

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 47192 KB Output is correct
2 Correct 20 ms 47412 KB Output is correct
3 Correct 21 ms 47416 KB Output is correct
4 Correct 20 ms 47196 KB Output is correct
5 Correct 19 ms 47192 KB Output is correct
6 Correct 18 ms 47192 KB Output is correct
7 Correct 20 ms 47192 KB Output is correct
8 Correct 19 ms 47196 KB Output is correct
9 Correct 21 ms 47212 KB Output is correct
10 Correct 17 ms 47192 KB Output is correct
11 Correct 16 ms 47196 KB Output is correct
12 Correct 17 ms 47236 KB Output is correct
13 Correct 16 ms 47192 KB Output is correct
14 Correct 19 ms 47188 KB Output is correct
15 Correct 17 ms 47192 KB Output is correct
16 Correct 19 ms 47196 KB Output is correct
17 Correct 19 ms 47192 KB Output is correct
18 Correct 18 ms 47192 KB Output is correct
19 Correct 19 ms 47180 KB Output is correct
20 Correct 20 ms 47196 KB Output is correct
21 Correct 18 ms 47196 KB Output is correct
22 Incorrect 19 ms 47416 KB Output isn't correct
23 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 292 ms 67772 KB Output is correct
2 Incorrect 358 ms 76624 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 47452 KB Output is correct
2 Correct 20 ms 47192 KB Output is correct
3 Correct 19 ms 47208 KB Output is correct
4 Correct 17 ms 47192 KB Output is correct
5 Correct 18 ms 47196 KB Output is correct
6 Correct 17 ms 47192 KB Output is correct
7 Correct 18 ms 47196 KB Output is correct
8 Correct 18 ms 47268 KB Output is correct
9 Correct 16 ms 47192 KB Output is correct
10 Correct 18 ms 47356 KB Output is correct
11 Correct 17 ms 47408 KB Output is correct
12 Correct 18 ms 47232 KB Output is correct
13 Correct 19 ms 47196 KB Output is correct
14 Correct 18 ms 47192 KB Output is correct
15 Correct 19 ms 47196 KB Output is correct
16 Correct 19 ms 47388 KB Output is correct
17 Correct 17 ms 47196 KB Output is correct
18 Correct 17 ms 47224 KB Output is correct
19 Correct 18 ms 47196 KB Output is correct
20 Correct 21 ms 47188 KB Output is correct
21 Correct 22 ms 47440 KB Output is correct
22 Incorrect 19 ms 47416 KB Output isn't correct
23 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 47192 KB Output is correct
2 Correct 19 ms 47436 KB Output is correct
3 Correct 19 ms 47196 KB Output is correct
4 Correct 19 ms 47196 KB Output is correct
5 Correct 18 ms 47196 KB Output is correct
6 Correct 19 ms 47188 KB Output is correct
7 Correct 17 ms 47192 KB Output is correct
8 Correct 20 ms 47416 KB Output is correct
9 Correct 21 ms 47196 KB Output is correct
10 Correct 20 ms 47196 KB Output is correct
11 Correct 19 ms 47196 KB Output is correct
12 Correct 18 ms 47196 KB Output is correct
13 Correct 18 ms 47196 KB Output is correct
14 Correct 17 ms 47196 KB Output is correct
15 Correct 18 ms 47392 KB Output is correct
16 Correct 18 ms 47192 KB Output is correct
17 Correct 19 ms 47304 KB Output is correct
18 Correct 19 ms 47196 KB Output is correct
19 Correct 17 ms 47260 KB Output is correct
20 Correct 20 ms 47320 KB Output is correct
21 Correct 21 ms 47400 KB Output is correct
22 Incorrect 16 ms 47196 KB Output isn't correct
23 Halted 0 ms 0 KB -