제출 #874132

#제출 시각아이디문제언어결과실행 시간메모리
874132HuyQuang_re_Zero말 (IOI15_horses)C++14
100 / 100
520 ms62120 KiB
#include <bits/stdc++.h> #define ll long long #define db long double #define II pair <ll,ll> #define III pair <ll,II> #define IV pair <vector <int>,vector <int> > #define TII pair <treap*,treap*> #define fst first #define snd second #define BIT(x,i) ((x>>i)&1) #define pi acos(-1) #define to_radian(x) (x*pi/180.0) #define to_degree(x) (x*180.0/pi) #define Log(x) (31-__builtin_clz((int)x)) #define LogLL(x) (63-__builtin_clzll((ll)x)) #include "horses.h" using namespace std; const ll mod=round(1e9)+7; set <int> s; struct pt { ll x,y; }; pt operator + (pt a,pt b) { return { a.x*b.x%mod,max(a.y,b.y) }; } int x[500005],y[500005],n,i,u,q,type,pos,val; struct Interval_Tree { pt st[4*500005]; void update(int id,int l,int r,int u) { if(l==r) { st[id]={ x[u],y[u] }; return ; } int mid=(l+r)>>1; if(u<=mid) update(id*2,l,mid,u); else update(id*2+1,mid+1,r,u); st[id]=st[id*2]+st[id*2+1]; } pt get(int id,int l,int r,int u,int v) { if(u>r || v<l) return { 1,0 }; if(u<=l && r<=v) return st[id]; int mid=(l+r)>>1; return get(id*2,l,mid,u,v)+get(id*2+1,mid+1,r,u,v); } } IT; int Cal() { set <int>::iterator it=s.end(); ll ma=0,res=0,last=n+1; while(it!=s.begin()) { it--; int u=*it; ll k=IT.get(1,1,n,u,last-1).y; if(ma<k) { ma=k; res=IT.get(1,1,n,1,u).x*ma%mod; } ma=ma*x[u]; if(ma>round(1e9)) break; last=u; } return res; } int init(int _n,int _x[],int _y[]) { n=_n; s.insert(0); for(i=n;i>=1;i--) { x[i]=_x[i-1],y[i]=_y[i-1]; if(x[i]>=2) s.insert(i); IT.update(1,1,n,i); } x[0]=1; return Cal(); } int updateX(int u,int k) { u++; s.erase(u); x[u]=k; if(x[u]>=2) s.insert(u); IT.update(1,1,n,u); return Cal(); } int updateY(int u,int k) { u++; y[u]=k; IT.update(1,1,n,u); return Cal(); } /* int main() { freopen("horse.inp","r",stdin); freopen("horse.out","w",stdout); ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin>>n; for(i=0;i<n;i++) cin>>x[i]; for(i=0;i<n;i++) cin>>y[i]; cout<<init(n,x,y)<<'\n'; cin>>q; while(q--) { cin>>type>>pos>>val; if(type==1) cout<<updateX(pos,val)<<'\n'; else cout<<updateY(pos,val)<<'\n'; } } */

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

horses.cpp: In member function 'void Interval_Tree::update(int, int, int, int)':
horses.cpp:26:40: warning: declaration of 'u' shadows a global declaration [-Wshadow]
   26 |     void update(int id,int l,int r,int u)
      |                                    ~~~~^
horses.cpp:22:29: note: shadowed declaration is here
   22 | int x[500005],y[500005],n,i,u,q,type,pos,val;
      |                             ^
horses.cpp: In member function 'pt Interval_Tree::get(int, int, int, int, int)':
horses.cpp:34:35: warning: declaration of 'u' shadows a global declaration [-Wshadow]
   34 |     pt get(int id,int l,int r,int u,int v)
      |                               ~~~~^
horses.cpp:22:29: note: shadowed declaration is here
   22 | int x[500005],y[500005],n,i,u,q,type,pos,val;
      |                             ^
horses.cpp: In function 'int Cal()':
horses.cpp:49:13: warning: declaration of 'u' shadows a global declaration [-Wshadow]
   49 |         int u=*it;
      |             ^
horses.cpp:22:29: note: shadowed declaration is here
   22 | int x[500005],y[500005],n,i,u,q,type,pos,val;
      |                             ^
horses.cpp:50:33: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   50 |         ll k=IT.get(1,1,n,u,last-1).y;
      |                             ~~~~^~
horses.cpp:57:12: warning: conversion from 'long long int' to 'double' may change value [-Wconversion]
   57 |         if(ma>round(1e9)) break;
      |            ^~
horses.cpp:60:12: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   60 |     return res;
      |            ^~~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:75:17: warning: declaration of 'u' shadows a global declaration [-Wshadow]
   75 | int updateX(int u,int k)
      |             ~~~~^
horses.cpp:22:29: note: shadowed declaration is here
   22 | int x[500005],y[500005],n,i,u,q,type,pos,val;
      |                             ^
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:84:17: warning: declaration of 'u' shadows a global declaration [-Wshadow]
   84 | int updateY(int u,int k)
      |             ~~~~^
horses.cpp:22:29: note: shadowed declaration is here
   22 | int x[500005],y[500005],n,i,u,q,type,pos,val;
      |                             ^
#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...