제출 #414795

#제출 시각아이디문제언어결과실행 시간메모리
414795Bill_00말 (IOI15_horses)C++14
0 / 100
94 ms40260 KiB
#include "horses.h" #include <bits/stdc++.h> #define MOD 1000000007 typedef long long ll; using namespace std; long long y[500005],x[500005],rightt[500005],leftt[500005]; long long pro[5000000],n,mx[5000000]; set<pair<ll,ll> >s; void build1(long long id,long long l,long long r){ if(l==r){ mx[id]=y[l]; return; } ll m=(l+r)>>1; build1(id*2,l,m); build1(id*2+1,m+1,r); mx[id]=max(mx[id*2],mx[id*2+1]); } void build(long long id,long long l,long long r){ if(l==r){ pro[id]=y[l]; return; } long long m=(l+r)>>1; build(id*2,l,m); build(id*2+1,m+1,r); pro[id]=pro[id*2]*pro[id*2+1]; if(pro[id]>=MOD) pro[id]%=MOD; } long long query(long long id,long long l,long long r,long long L,long long R){ if(R<L) return 1; if(r<L || R<l) return 1; if(L<=l && r<=R) return pro[id]; long long m=(l+r)>>1; return (query(id*2,l,m,L,R)*query(id*2+1,m+1,r,L,R))%MOD; } long long query1(ll id,ll l,ll r,ll L,ll R){ if(R<l || r<L) return 0; if(L<=l && r<=R) return mx[id]; ll m=(l+r)>>1; return max(query1(id*2,l,m,L,R),query1(id*2+1,m+1,r,L,R)); } void update(ll id,ll l,ll r,ll d,ll e){ if(l==r){ pro[id]=e; return; } ll m=(l+r)>>1; if(m>=d) update(id*2,l,m,d,e); else update(id*2+1,m+1,r,d,e); pro[id]=pro[id*2]*pro[id*2+1]; if(pro[id]>=MOD) pro[id]%=MOD; } void update1(ll id,ll l,ll r,ll d,ll e){ if(l==r){ mx[id]=e; return; } ll m=(l+r)>>1; if(m>=d) update1(id*2,l,m,d,e); else update1(id*2+1,m+1,r,d,e); mx[id]=max(mx[id*2],mx[id*2+1]); } int init(int N,int X[],int Y[]){ memset(leftt,-1,sizeof(leftt)); memset(rightt,-1,sizeof(rightt)); n=(long long)N; for(long long i=0;i<n;i++){ y[i]=(long long)Y[i]; x[i]=(long long)X[i]; } build(1,0,n-1); build1(1,0,n-1); bool flag=0; long long l; for(long long i=0;i<n;i++){ if(x[i]==1 && flag==0){ flag=1; l=i; } if(x[i]!=1 && flag==1){ flag=0; s.insert({l,i-1}); rightt[l]=i-1; leftt[i-1]=l; } } if(flag==1){ rightt[l]=n-1; leftt[n-1]=l; s.insert({l,n-1}); } long long c=y[n-1]; pair<long double,ll>p={0,-1}; for(ll i=n-1;i>=0;i--){ ll val=y[i]; if(leftt[i]==-1){ i=leftt[i]; val=query1(1,0,n-1,i,rightt[i]); } p=max(p,{(long double)(c)/(long double)(val),i}); c*=x[i]; if(c>=1000000000) break; } ll ans=query(1,0,n-1,0,p.second); ll id=p.second,val=y[id]; if(rightt[id]!=-1) val=query1(1,0,n-1,id,rightt[id]); return (ans*val)%MOD; } int updateX(int pos, int val){ update(1,0,n-1,pos,val); x[pos]=val; if(val==1){ pair<ll,ll>temp={pos,1000000000}; auto it=s.lower_bound(temp); --it; if(it->first>pos || pos>it->second){ leftt[pos]=pos; rightt[pos]=pos; s.insert({leftt[pos],rightt[pos]}); if(pos>0 && leftt[pos-1]!=-1){ rightt[leftt[pos-1]]=rightt[pos]; leftt[rightt[pos]]=leftt[pos-1]; s.erase({leftt[pos-1],pos-1}); s.erase({pos,rightt[pos]}); s.insert({leftt[pos-1],rightt[pos]}); rightt[pos]=-1; leftt[pos-1]=-1; } if(pos<(n-1) && rightt[pos+1]!=-1){ rightt[leftt[pos]]=rightt[pos+1]; leftt[rightt[pos+1]]=leftt[pos]; s.erase({leftt[pos],pos}); s.erase({pos+1,rightt[pos+1]}); s.insert({leftt[pos],rightt[pos+1]}); rightt[pos+1]=-1; leftt[pos]=-1; } } } else{ pair<ll,ll>temp={pos,1000000000}; auto it=s.lower_bound(temp); --it; if(it->first<=pos && pos<=it->second){ ll st=it->first; ll en=it->second; s.erase(it); leftt[en]=-1; rightt[st]=-1; if(st!=pos){ rightt[st]=pos-1; leftt[pos-1]=st; s.insert({st,pos-1}); } if(en!=pos){ leftt[en]=pos+1; rightt[pos+1]=en; s.insert({pos+1,en}); } } } long long c=y[n-1]; pair<long double,ll>p={0,-1}; for(ll i=n-1;i>=0;i--){ ll value=y[i]; if(leftt[i]==-1){ i=leftt[i]; value=query1(1,0,n-1,i,rightt[i]); } p=max(p,{(long double)(c)/(long double)(value),i}); c*=x[i]; if(c>=1000000000) break; } ll ans=query(1,0,n-1,0,p.second); ll id=p.second,value=y[id]; if(rightt[id]!=-1) value=query1(1,0,n-1,id,rightt[id]); return (ans*value)%MOD; } int updateY(int pos, int val) { update1(1,0,n-1,pos,val); y[pos]=val; long long c=y[n-1]; pair<long double,ll>p={0,-1}; for(ll i=n-1;i>=0;i--){ ll value=y[i]; if(leftt[i]==-1){ i=leftt[i]; value=query1(1,0,n-1,i,rightt[i]); } p=max(p,{(long double)(c)/(long double)(value),i}); c*=x[i]; if(c>=1000000000) break; } ll ans=query(1,0,n-1,0,p.second); ll id=p.second,value=y[id]; if(rightt[id]!=-1) value=query1(1,0,n-1,id,rightt[id]); return (ans*value)%MOD; }

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

horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:108:18: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  108 |  return (ans*val)%MOD;
      |                  ^
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:179:20: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  179 |  return (ans*value)%MOD;
      |                    ^
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:200:20: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  200 |  return (ans*value)%MOD;
      |                    ^
horses.cpp:191:16: warning: array subscript -1 is below array bounds of 'long long int [500005]' [-Warray-bounds]
  191 |    value=query1(1,0,n-1,i,rightt[i]);
      |          ~~~~~~^~~~~~~~~~~~~~~~~~~~~
horses.cpp:6:31: note: while referencing 'rightt'
    6 | long long y[500005],x[500005],rightt[500005],leftt[500005];
      |                               ^~~~~~
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:99:14: warning: array subscript -1 is below array bounds of 'long long int [500005]' [-Warray-bounds]
   99 |    val=query1(1,0,n-1,i,rightt[i]);
      |        ~~~~~~^~~~~~~~~~~~~~~~~~~~~
horses.cpp:6:31: note: while referencing 'rightt'
    6 | long long y[500005],x[500005],rightt[500005],leftt[500005];
      |                               ^~~~~~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:170:16: warning: array subscript -1 is below array bounds of 'long long int [500005]' [-Warray-bounds]
  170 |    value=query1(1,0,n-1,i,rightt[i]);
      |          ~~~~~~^~~~~~~~~~~~~~~~~~~~~
horses.cpp:6:31: note: while referencing 'rightt'
    6 | long long y[500005],x[500005],rightt[500005],leftt[500005];
      |                               ^~~~~~
#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...