| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 857304 |
2023-10-05T20:32:49 Z |
Huseyn123 |
Horses (IOI15_horses) |
C++17 |
|
150 ms |
34920 KB |
#include <bits/stdc++.h>
#include "horses.h"
#define MAX 1000001
#define INF LLONG_MAX
#define MOD 1000000007
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define ins insert
#define ff first
#define ss second
#define gett(x,m) get<m>(x)
#define all(a) a.begin(),a.end()
#define lb(a,b) lower_bound(all(a),b)
#define ub(a,b) upper_bound(all(a),b)
#define sortv(a) sort(all(a))
#define sorta(a,sz) sort(a,a+sz)
#define inputar(a,b){\
for(int i=0;i<b;i++){\
cin >> a[i];\
}\
}
#define inputvec(a,b){\
for(int i=0;i<b;i++){\
ll num;\
cin >> num;\
a.pb(num);\
}\
}
#define outputar(a,b){\
for(int i=0;i<b;i++){\
cout << a[i] << " ";\
}\
cout << "\n";\
}
#define outputvec(a){\
for(auto x:a){\
cout << x << " ";\
}\
cout << "\n";\
}
#define reset(a,n,v){\
for(int i=0;i<n;i++){\
a[i]=v;\
}\
}
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef tuple<ll,ll,ll> tll;
typedef pair<ll,ll> pll;
typedef pair<int,int> pii;
typedef double db;
typedef long double ldb;
struct segtree{
vector<ll> maxs;
vector<ll> lazy;
int size;
void init(int n){
size=1;
while(size<n){
size*=2;
}
maxs.assign(2*size,0LL);
lazy.assign(2*size,1LL);
}
void build(int x,int lx,int rx,vector<int> &a){
if(rx-lx==1){
if(lx<(int)a.size()){
maxs[x]=a[lx];
}
return;
}
int m=(lx+rx)/2;
build(2*x+1,lx,m,a);
build(2*x+2,m,rx,a);
maxs[x]=max(maxs[2*x+1],maxs[2*x+2]);
}
void build(vector<int> &a){
build(0,0,size,a);
}
void propogate(int x,int lx,int rx){
if(rx-lx==1){
return;
}
maxs[2*x+1]*=lazy[x];
maxs[2*x+1]%=MOD;
maxs[2*x+2]*=lazy[x];
maxs[2*x+2]%=MOD;
lazy[2*x+1]*=lazy[x];
lazy[2*x+1]%=MOD;
lazy[2*x+2]*=lazy[x];
lazy[2*x+2]%=MOD;
lazy[x]=1;
}
void upd(int x,int lx,int rx,int l,int r,int v){
propogate(x,lx,rx);
if(rx<=l || lx>=r){
return;
}
if(lx>=l && rx<=r){
maxs[x]*=v;
maxs[x]%=MOD;
lazy[x]*=v;
lazy[x]%=MOD;
return;
}
int m=(lx+rx)/2;
upd(2*x+1,lx,m,l,r,v);
upd(2*x+2,m,rx,l,r,v);
maxs[x]=(maxs[2*x+1],maxs[2*x+2]);
}
void upd(int l,int r,int v){
return upd(0,0,size,l,r,v);
}
ll get(int x,int lx,int rx,int l,int r){
propogate(x,lx,rx);
if(rx<=l || lx>=r){
return 0;
}
if(lx>=l && rx<=r){
return maxs[x];
}
int m=(lx+rx)/2;
ll s1,s2;
s1=get(2*x+1,lx,m,l,r);
s2=get(2*x+2,m,rx,l,r);
return max(s1,s2);
}
ll get(int l,int r){
return get(0,0,size,l,r);
}
};
ll powmod(ll x,ll y,ll md){
if(y==0){
return 1;
}
x%=md;
if(x==0){
return 0;
}
ll res=1;
while(y>0){
if(y%2){
res*=x;
res%=md;
}
y/=2;
x*=x;
x%=md;
}
return res;
}
ll inv(ll n,ll md){
return powmod(n,md-2,md);
}
ll X1[MAX],Y1[MAX],n;
segtree st;
int init(int N, int X[], int Y[]) {
n=N;
for(int i=0;i<N;i++){
X1[i]=X[i];
Y1[i]=Y[i];
}
st.init(N);
vector<int> a(N);
ll h=1;
for(int i=0;i<N;i++){
h*=X1[i];
h%=MOD;
a[i]=(h*Y1[i])%MOD;
}
st.build(a);
return 0;
}
int updateX(int pos, int val) {
st.upd(pos,n,inv(X1[pos],MOD));
st.upd(pos,n,val);
X1[pos]=val;
return st.get(0,n);
}
int updateY(int pos, int val) {
st.upd(pos,pos+1,inv(Y1[pos],MOD));
st.upd(pos,pos+1,val);
Y1[pos]=val;
return st.get(0,n);
}
Compilation message
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:171:17: warning: conversion from 'll' {aka 'long long int'} to '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'} may change value [-Wconversion]
171 | a[i]=(h*Y1[i])%MOD;
| ^
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:177:13: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
177 | st.upd(pos,n,inv(X1[pos],MOD));
| ^
horses.cpp:177:18: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
177 | st.upd(pos,n,inv(X1[pos],MOD));
| ~~~^~~~~~~~~~~~~
horses.cpp:178:13: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
178 | st.upd(pos,n,val);
| ^
horses.cpp:180:18: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
180 | return st.get(0,n);
| ^
horses.cpp:180:15: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
180 | return st.get(0,n);
| ~~~~~~^~~~~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:184:22: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
184 | st.upd(pos,pos+1,inv(Y1[pos],MOD));
| ~~~^~~~~~~~~~~~~
horses.cpp:187:18: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
187 | return st.get(0,n);
| ^
horses.cpp:187:15: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
187 | return st.get(0,n);
| ~~~~~~^~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
2392 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
2392 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
150 ms |
34920 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
2392 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
2548 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
