제출 #710940

#제출 시각아이디문제언어결과실행 시간메모리
710940ToroTN말 (IOI15_horses)C++14
17 / 100
456 ms37184 KiB
#include<bits/stdc++.h> using namespace std; #include "horses.h" //#include "grader.cpp" #define ll long long ll MOD=1000000007; ll n,x[500005],y[500005],mul[2000005]; void build_mul(ll tree,ll st,ll ed) { ll md=(st+ed)/2; if(st==ed) { mul[tree]=x[st]; return; } build_mul(2*tree,st,md); build_mul(2*tree+1,md+1,ed); if(mul[2*tree]==-1||mul[2*tree+1]==-1) { mul[tree]=-1; }else if(mul[2*tree]*mul[2*tree+1]>1e9) { mul[tree]=-1; }else { mul[tree]=mul[2*tree]*mul[2*tree+1]; } } void update_mul(ll tree,ll st,ll ed,ll idx,ll val) { ll md=(st+ed)/2; if(st==ed) { mul[tree]=val; return; } if(idx<=md) { update_mul(2*tree,st,md,idx,val); }else { update_mul(2*tree+1,md+1,ed,idx,val); } if(mul[2*tree]==-1||mul[2*tree+1]==-1) { mul[tree]=-1; }else if(mul[2*tree]*mul[2*tree+1]>1e9) { mul[tree]=-1; }else { mul[tree]=mul[2*tree]*mul[2*tree+1]; } } ll query_mul(ll tree,ll st,ll ed,ll l,ll r) { ll md=(st+ed)/2; if(st>r||ed<l)return 1; if(st>=l&&ed<=r)return mul[tree]; ll lft=query_mul(2*tree,st,md,l,r),rht=query_mul(2*tree+1,md+1,ed,l,r); if(lft==-1||rht==-1)return -1; if(lft*rht>1e9)return -1; return lft*rht; } ll seg[2000005],ans[2000005]; void build(ll tree,ll st,ll ed) { ll md=(st+ed)/2; if(st==ed) { seg[tree]=st; return; } build(2*tree,st,md); build(2*tree+1,md+1,ed); ll l_idx=seg[2*tree],r_idx=seg[2*tree+1]; ll rng=query_mul(1,1,n,l_idx+1,r_idx); if(rng!=-1) { if(rng*y[r_idx]>1e9) { rng=-1; }else { rng*=y[r_idx]; } } if(rng==-1) { seg[tree]=r_idx; }else { if(rng>y[l_idx]) { seg[tree]=r_idx; }else { seg[tree]=l_idx; } } } void update(ll tree,ll st,ll ed,ll idx) { ll md=(st+ed)/2; if(st==ed) { seg[tree]=idx; return; } if(idx<=md) { update(2*tree,st,md,idx); }else { update(2*tree+1,md+1,ed,idx); } ll l_idx=seg[2*tree],r_idx=seg[2*tree+1]; ll rng=query_mul(1,1,n,l_idx+1,r_idx); if(rng!=-1) { if(rng*y[r_idx]>1e9) { rng=-1; }else { rng*=y[r_idx]; } } if(rng==-1) { seg[tree]=r_idx; }else { if(rng>y[l_idx]) { seg[tree]=r_idx; }else { seg[tree]=l_idx; } } } int init(int N, int X[], int Y[]) { n=N;for(int i=1;i<=n;i++)x[i]=X[i-1],y[i]=Y[i-1]; ans[1]=x[1]; for(int i=2;i<=n;i++)ans[i]=ans[i-1]*x[i],ans[i]%=MOD; for(int i=1;i<=n;i++)ans[i]*=y[i],ans[i]%=MOD; /*for(int i=1;i<=n;i++) { printf("%lld ",ans[i]); } printf("\n");*/ build_mul(1,1,n); build(1,1,n); //printf("%lld\n",mul[1]); return ans[seg[1]]; } int updateX(int pos, int val) { ++pos; x[pos]=val; update_mul(1,1,n,pos,val); update(1,1,n,pos); return ans[seg[1]]; } int updateY(int pos, int val) { ++pos; y[pos]=val; update(1,1,n,pos); return ans[seg[1]]; }

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

horses.cpp: In function 'void build_mul(long long int, long long int, long long int)':
horses.cpp:21:25: warning: conversion from 'long long int' to 'double' may change value [-Wconversion]
   21 |     }else if(mul[2*tree]*mul[2*tree+1]>1e9)
      |              ~~~~~~~~~~~^~~~~~~~~~~~~~
horses.cpp: In function 'void update_mul(long long int, long long int, long long int, long long int, long long int)':
horses.cpp:47:25: warning: conversion from 'long long int' to 'double' may change value [-Wconversion]
   47 |     }else if(mul[2*tree]*mul[2*tree+1]>1e9)
      |              ~~~~~~~~~~~^~~~~~~~~~~~~~
horses.cpp: In function 'long long int query_mul(long long int, long long int, long long int, long long int, long long int)':
horses.cpp:62:11: warning: conversion from 'long long int' to 'double' may change value [-Wconversion]
   62 |     if(lft*rht>1e9)return -1;
      |        ~~~^~~~
horses.cpp: In function 'void build(long long int, long long int, long long int)':
horses.cpp:80:15: warning: conversion from 'long long int' to 'double' may change value [-Wconversion]
   80 |         if(rng*y[r_idx]>1e9)
      |            ~~~^~~~~~~~~
horses.cpp: In function 'void update(long long int, long long int, long long int, long long int)':
horses.cpp:121:15: warning: conversion from 'long long int' to 'double' may change value [-Wconversion]
  121 |         if(rng*y[r_idx]>1e9)
      |            ~~~^~~~~~~~~
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:157:22: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  157 |     return ans[seg[1]];
      |            ~~~~~~~~~~^
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:166:22: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  166 |     return ans[seg[1]];
      |            ~~~~~~~~~~^
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:174:22: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  174 |     return ans[seg[1]];
      |            ~~~~~~~~~~^
#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...