제출 #154829

#제출 시각아이디문제언어결과실행 시간메모리
154829junodeveloper말 (IOI15_horses)C++14
17 / 100
399 ms40876 KiB
#include "horses.h" #include <bits/stdc++.h> using namespace std; typedef long long ll; const int off=1<<19; const int mod=1e9+7; struct MULT { int tree[off<<1]; MULT() {memset(tree,0,sizeof(tree));} void update(int p,int x) { p+=off; tree[p]=x;p/=2; while(p>0) { tree[p]=(ll)tree[p<<1]*tree[p<<1|1]%mod; p>>=1; } } int query(int l,int r) { int ret=1; l+=off,r+=off; while(l<r) { if(l%2==1) ret=(ll)ret*tree[l++]%mod; if(r%2==0) ret=(ll)ret*tree[r--]%mod; l>>=1,r>>=1; } if(l==r) ret=(ll)ret*tree[l]%mod; return ret; } } mult; struct MAXT { int tree[off<<1]; MAXT() {memset(tree,0,sizeof(tree));} void update(int p,int x) { p+=off; tree[p]=x;p/=2; while(p>0) { tree[p]=max(tree[p<<1],tree[p<<1|1]); p>>=1; } } int query(int l,int r) { int ret=0; l+=off,r+=off; while(l<r) { if(l%2==1) ret=max(ret,tree[l++]); if(r%2==0) ret=max(ret,tree[r--]); l>>=1,r>>=1; } if(l==r) ret=max(ret,tree[l]); return ret; } } maxt; int n; int *x, *y; set<int> st; int solve() { auto it=st.end(); int i,j; ll r=1; while(it!=st.begin()&&r*x[*prev(it)]<=(ll)1e9) { it--; r*=x[*it]; } int fir=*it; r=1; ll mx=0; while(it!=st.end()) { i=*it; r*=x[i]; if(next(it)==st.end()) j=n-1; else j=*next(it)-1; mx=max(mx,(ll)r*maxt.query(i,j)); it++; } return (ll)mult.query(0,fir-1)*mx%mod; } int init(int N, int X[], int Y[]) { n=N; x=X,y=Y; int i; for(i=0;i<n;i++) { mult.update(i,x[i]); maxt.update(i,y[i]); if(x[i]!=1) st.insert(i); } st.insert(0); return solve(); } int updateX(int pos, int val) { if(pos&&x[pos]!=1) { st.erase(pos); } x[pos]=val; if(pos&&x[pos]!=1) { st.insert(pos); } mult.update(pos,val); return solve(); } int updateY(int pos, int val) { y[pos]=val; maxt.update(pos,val); return solve(); }

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

horses.cpp: In member function 'void MULT::update(int, int)':
horses.cpp:17:39: warning: conversion to 'int' from 'll {aka long long int}' may alter its value [-Wconversion]
    tree[p]=(ll)tree[p<<1]*tree[p<<1|1]%mod;
            ~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~
horses.cpp: In member function 'int MULT::query(int, int)':
horses.cpp:25:36: warning: conversion to 'int' from 'll {aka long long int}' may alter its value [-Wconversion]
    if(l%2==1) ret=(ll)ret*tree[l++]%mod;
                   ~~~~~~~~~~~~~~~~~^~~~
horses.cpp:26:36: warning: conversion to 'int' from 'll {aka long long int}' may alter its value [-Wconversion]
    if(r%2==0) ret=(ll)ret*tree[r--]%mod;
                   ~~~~~~~~~~~~~~~~~^~~~
horses.cpp:29:31: warning: conversion to 'int' from 'll {aka long long int}' may alter its value [-Wconversion]
   if(l==r) ret=(ll)ret*tree[l]%mod;
                ~~~~~~~~~~~~~~~^~~~
horses.cpp: In function 'int solve()':
horses.cpp:78:35: warning: conversion to 'int' from 'll {aka long long int}' may alter its value [-Wconversion]
  return (ll)mult.query(0,fir-1)*mx%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...