제출 #31204

#제출 시각아이디문제언어결과실행 시간메모리
31204cscandkswon말 (IOI15_horses)C++14
17 / 100
896 ms41156 KiB
#include "horses.h" #include <bits/stdc++.h> using namespace std; const int MAXN=500005; const long long MOD=(1e9)+7; int T[MAXN*3], M[MAXN*3], N, *X, *Y; set<int, greater<int> > S; void initTree(int idx, int l, int r){ if(l==r){ T[idx]=Y[l]; return; } int m=(l+r)>>1, lidx=idx<<1, ridx=lidx+1; initTree(lidx, l, m); initTree(ridx, m+1, r); T[idx]=max(T[lidx], T[ridx]); } void updateTree(int idx, int l, int r, int t){ if(l==r){ T[idx]=Y[t]; return; } int m=(l+r)>>1, lidx=idx<<1, ridx=lidx+1; if(t<=m) updateTree(lidx, l, m, t); if(t>m) updateTree(ridx, m+1, r, t); T[idx]=max(T[lidx], T[ridx]); } int queryTree(int idx, int l, int r, int s, int e){ if(r<s || l>e) return 0; if(s<=l && r<=e) return T[idx]; int m=(l+r)>>1, lidx=idx<<1, ridx=lidx+1; return max(queryTree(lidx, l, m, s, e), queryTree(ridx, m+1, r, s, e)); } void initmultiply(int idx, int l, int r){ if(l==r){ M[idx]=X[l]; return; } int lidx=idx<<1, ridx=lidx+1, m=(l+r)>>1; initmultiply(lidx, l, m); initmultiply(ridx, m+1, r); M[idx]=(long long)M[lidx]*M[ridx]%MOD; } void updatemultiply(int idx, int l, int r, int t){ if(l==r){ M[idx]=X[t]; return; } int m=(l+r)>>1, lidx=idx<<1, ridx=lidx+1; if(t<=m) updatemultiply(lidx, l, m, t); if(t>m) updatemultiply(ridx, m+1, r, t); M[idx]=(long long)M[lidx]*M[ridx]%MOD; } int getmultiply(int idx, int l, int r, int s, int e){ if(r<s|| l>e) return 1; if(s<=l && r<=e) return M[idx]; int m=(l+r)>>1, lidx=idx<<1, ridx=lidx+1; return (long long)getmultiply(lidx, l, m, s, e)*getmultiply(ridx, m+1, r, s, e)%MOD; } int getans(){ long long x=1, y, ans=0, ansy; set<int, greater<int> >::iterator pos, nxt, idx; for(pos=S.begin(); pos!=S.end(); ++pos){ x=x*X[*pos]; if(x>1e9) break; } x=1; if(pos==S.end()) --pos; if(pos!=S.begin()){ nxt=pos; --nxt; for(; pos!=S.begin(); pos=nxt, --nxt){ x=x*X[*pos]; if(x*(y=queryTree(1, 0, N-1, *pos, (*nxt)-1))>ans){ ans=x*y; ansy=y; idx=pos; } } } pos=S.begin(); x=x*X[*pos]; if(x*(y=queryTree(1, 0, N-1, *pos, N-1))>ans){ ans=x*y; ansy=y; idx=pos; } return getmultiply(1, 0, N-1, 0, *idx)*ansy%MOD; } int init(int _N, int _X[], int _Y[]) { int i; N=_N, X=_X, Y=_Y; initTree(1, 0, N-1); initmultiply(1, 0, N-1); for(i=0; i<N; i++) if(X[i]>1) S.insert(i); S.insert(0); return getans(); } int updateX(int pos, int val) { if(X[pos]>1 && val==1 && pos) S.erase(pos); else if(X[pos]==1 && val>1) S.insert(pos); X[pos]=val; updatemultiply(1, 0, N-1, pos); return getans(); } int updateY(int pos, int val) { Y[pos]=val; updateTree(1, 0, N-1, pos); return getans(); }

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

horses.cpp: In function 'void initmultiply(int, int, int)':
horses.cpp:47:11: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
     M[idx]=(long long)M[lidx]*M[ridx]%MOD;
           ^
horses.cpp: In function 'void updatemultiply(int, int, int, int)':
horses.cpp:58:11: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
     M[idx]=(long long)M[lidx]*M[ridx]%MOD;
           ^
horses.cpp: In function 'int getmultiply(int, int, int, int, int)':
horses.cpp:65:85: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
     return (long long)getmultiply(lidx, l, m, s, e)*getmultiply(ridx, m+1, r, s, e)%MOD;
                                                                                     ^
horses.cpp: In function 'int getans()':
horses.cpp:95:49: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
     return getmultiply(1, 0, N-1, 0, *idx)*ansy%MOD;
                                                 ^
horses.cpp:95:43: warning: 'ansy' may be used uninitialized in this function [-Wmaybe-uninitialized]
     return getmultiply(1, 0, N-1, 0, *idx)*ansy%MOD;
                                           ^
#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...