제출 #857318

#제출 시각아이디문제언어결과실행 시간메모리
857318Huseyn123말 (IOI15_horses)C++17
17 / 100
147 ms34908 KiB
#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<ll> &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<ll> &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]=max(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<ll> 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); int res1=st.get(0,n); return res1; } int updateX(int pos, int val) { st.upd(pos,n,inv(X1[pos],MOD)); st.upd(pos,n,val); X1[pos]=val; int res1=st.get(0,n); return res1; } int updateY(int pos, int val) { st.upd(pos,pos+1,inv(Y1[pos],MOD)); st.upd(pos,pos+1,val); Y1[pos]=val; int res1=st.get(0,n); return res1; }

컴파일 시 표준 에러 (stderr) 메시지

horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:174:20: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  174 |  int res1=st.get(0,n);
      |                    ^
horses.cpp:174:17: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  174 |  int res1=st.get(0,n);
      |           ~~~~~~^~~~~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:178:13: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  178 |  st.upd(pos,n,inv(X1[pos],MOD));
      |             ^
horses.cpp:178:18: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  178 |  st.upd(pos,n,inv(X1[pos],MOD));
      |               ~~~^~~~~~~~~~~~~
horses.cpp:179:13: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  179 |  st.upd(pos,n,val);
      |             ^
horses.cpp:181:20: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  181 |  int res1=st.get(0,n);
      |                    ^
horses.cpp:181:17: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  181 |  int res1=st.get(0,n);
      |           ~~~~~~^~~~~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:186:22: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  186 |  st.upd(pos,pos+1,inv(Y1[pos],MOD));
      |                   ~~~^~~~~~~~~~~~~
horses.cpp:189:20: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  189 |  int res1=st.get(0,n);
      |                    ^
horses.cpp:189:17: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  189 |  int res1=st.get(0,n);
      |           ~~~~~~^~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...