제출 #245747

#제출 시각아이디문제언어결과실행 시간메모리
245747Evirir말 (IOI15_horses)C++17
17 / 100
1593 ms32436 KiB
#include "horses.h" #include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace std; using namespace __gnu_pbds; #define watch(x) cout<<(#x)<<"="<<(x)<<'\n' #define mset(d,val) memset(d,val,sizeof(d)) #define setp(x) cout<<fixed<<setprecision(x) #define forn(i,a,b) for(int i=(a);i<(b);i++) #define fore(i,a,b) for(int i=(a);i<=(b);i++) #define pb push_back #define F first #define S second #define pqueue priority_queue #define fbo find_by_order #define ook order_of_key typedef long long ll; typedef pair<ll,ll> ii; typedef vector<ll> vi; typedef vector<ii> vii; typedef long double ld; typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> pbds; void amin(ll &a, ll b){ a=min(a,b); } void amax(ll &a, ll b){ a=max(a,b); } void YES(){cout<<"YES\n";} void NO(){cout<<"NO\n";} void SD(int t=0){ cout<<"PASSED "<<t<<endl; } const ll INF = ll(1e18); const int MOD = 1e9+7; ll add(ll a,ll b) { a+=b;a%=MOD; if(a<0) a+=MOD; return a; } ll mult(ll a, ll b) { a%=MOD; b%=MOD; ll ans=(a*b)%MOD; if(ans<0) ans+=MOD; return ans; } ll pw(ll a, ll b) { ll r=1; while(b){ if(b&1) r=mult(r,a); a=mult(a,a); b>>=1; } return r; } ll inverse(ll a) { return pw(a,MOD-2); } class PointSegmentTree{ private: int size_; vector<ll> v; void update(int p, ll val, int k, int l, int r) { if(p < l || r < p) return; if(l == r){ v[k]=val; //modification return; } int mid = (l+r)>>1; update(p, val, k*2, l, mid); update(p, val, k*2+1, mid+1, r); v[k] = merge(v[k*2], v[k*2+1]); } ll query(int s, int e, int k, int l, int r) { if(e < l || r < s) return 1; //dummy value if(s <= l && r <= e) return v[k]; int mid = (l+r)>>1; ll lc = query(s, e, k*2, l, mid); ll rc = query(s, e, k*2+1, mid+1, r); return merge(lc, rc); } public: PointSegmentTree(): v(vector<ll>()) {} PointSegmentTree(int n){ for(size_=1;size_<n;) size_<<=1; v.resize(size_*4); } //void reset(){} inline ll merge(ll x, ll y){ return mult(x,y); } inline void update(int p, ll val){ update(p, val, 1, 0, size_-1); } inline ll query(int l, int r){ return query(l, r, 1, 0, size_-1); } }; bool DEBUG = 0; const int MAXN = 500005; int n; vi x,y; PointSegmentTree st; ll query() { ll pro=1; ll best=max(0,n-32); for(int i=best+1;i<n;i++) { pro*=x[i]; if(pro*y[i]>y[best]){ best=i; pro=1; } } cerr<<"best="<<best<<" st="<<st.query(0,best)<<" y[best]="<<y[best]<<'\n'; return mult(st.query(0,best), y[best]); } int init(int N, int X[], int Y[]) { int curmax=Y[0], curx=X[0]; for(int i=1;i<N;i++){ if(X[i]==1) curmax=max(curmax, Y[i]); else{ x.pb(curx); y.pb(curmax); curx=X[i]; curmax=Y[i]; } } x.pb(curx); y.pb(curmax); n=x.size(); st=PointSegmentTree(n); forn(i,0,n){ cerr<<"x["<<i<<"]="<<x[i]<<" y["<<i<<"]="<<y[i]<<'\n'; st.update(i,x[i]); } return query(); } int updateX(int pos, int val) { x[pos] = val; st.update(pos,val); return query(); } int updateY(int pos, int val) { y[pos] = val; return query(); }

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

horses.cpp: In function 'll query()':
horses.cpp:117:16: warning: conversion to 'int' from 'll {aka long long int}' may alter its value [-Wconversion]
  for(int i=best+1;i<n;i++)
            ~~~~^~
horses.cpp:125:46: warning: conversion to 'int' from 'll {aka long long int}' may alter its value [-Wconversion]
  cerr<<"best="<<best<<" st="<<st.query(0,best)<<" y[best]="<<y[best]<<'\n';
                                              ^
horses.cpp:126:29: warning: conversion to 'int' from 'll {aka long long int}' may alter its value [-Wconversion]
  return mult(st.query(0,best), y[best]);
                             ^
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:144:10: warning: conversion to 'int' from 'std::vector<long long int>::size_type {aka long unsigned int}' may alter its value [-Wconversion]
  n=x.size();
    ~~~~~~^~
horses.cpp:151:14: warning: conversion to 'int' from 'll {aka long long int}' may alter its value [-Wconversion]
  return query();
         ~~~~~^~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:158:14: warning: conversion to 'int' from 'll {aka long long int}' may alter its value [-Wconversion]
  return query();
         ~~~~~^~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:164:14: warning: conversion to 'int' from 'll {aka long long int}' may alter its value [-Wconversion]
  return query();
         ~~~~~^~
#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...