제출 #1107717

#제출 시각아이디문제언어결과실행 시간메모리
1107717Aviansh말 (IOI15_horses)C++17
0 / 100
90 ms24672 KiB
#include "horses.h" #include <bits/stdc++.h> using namespace std; int n; int *x; int *y; int mod = 1e9+7; template <class T> class segTree{ private: int n; T *st; public: void realMakeST(int *arr, int l, int r, int ind){ if(l==r){ st[ind]=arr[l]; } else{ int mid = (l+r)/2; realMakeST(arr,l,mid,ind*2+1); realMakeST(arr,mid+1,r,ind*2+2); st[ind]=st[ind*2+1]*st[ind*2+2]; st[ind]%=mod; } } segTree(){ //aise hi } segTree(int *arr, int siz){ int x = (int)pow(2,ceil(log2(siz))); n=siz-1; x*=2; st=new T[x]; realMakeST(arr,0,n,0); } void realUpdate(int l, int r, int ind, int pos, int val){ if(pos<l||pos>r){ return; } if(l==r){ st[ind]=val; return; } int mid = (l+r)/2; realUpdate(l,mid,2*ind+1,pos,val); realUpdate(mid+1,r,2*ind+2,pos,val); st[ind]=st[ind*2+1]*st[ind*2+2]; st[ind]%=mod; } void update(int ind, int val){ realUpdate(0,n,0,ind,val); } T realQuery(int l, int r, int s, int e, int ind){ if(e<l||s>r){ return 1; } if(s<=l&&r<=e){ return st[ind]; } int mid = (l+r)/2; return (realQuery(l,mid,s,e,2*ind+1)*realQuery(mid+1,r,s,e,2*ind+2))%mod; } T query(int s,int e){ return realQuery(0,n,s,e,0); } }; template <class T> class segTreeMax{ private: int n; T *st; public: void realMakeST(int *arr, int l, int r, int ind){ if(l==r){ st[ind]=arr[l]; } else{ int mid = (l+r)/2; realMakeST(arr,l,mid,ind*2+1); realMakeST(arr,mid+1,r,ind*2+2); st[ind]=st[ind*2+1]*st[ind*2+2]; st[ind]%=mod; } } segTreeMax(){ //aise hi } segTreeMax(int *arr, int siz){ int x = (int)pow(2,ceil(log2(siz))); n=siz-1; x*=2; st=new T[x]; realMakeST(arr,0,n,0); } void realUpdate(int l, int r, int ind, int pos, int val){ if(pos<l||pos>r){ return; } if(l==r){ st[ind]=val; return; } int mid = (l+r)/2; realUpdate(l,mid,2*ind+1,pos,val); realUpdate(mid+1,r,2*ind+2,pos,val); st[ind]=st[ind*2+1]*st[ind*2+2]; st[ind]%=mod; } void update(int ind, int val){ realUpdate(0,n,0,ind,val); } T realQuery(int l, int r, int s, int e, int ind){ if(e<l||s>r){ return 1; } if(s<=l&&r<=e){ return st[ind]; } int mid = (l+r)/2; return (realQuery(l,mid,s,e,2*ind+1)*realQuery(mid+1,r,s,e,2*ind+2))%mod; } T query(int s,int e){ return realQuery(0,n,s,e,0); } }; int t = 1; int *temp = &t; segTree<long long> st(temp,1); segTreeMax<long long> stmax(temp,1); set<pair<int,int>>ones; int finans(){ int mx = n-1; long long curr = 1; int mxy = y[n-1]; set<pair<int,int>>::iterator it = ones.end(); it--; for(int i = n-1;i>=0;i--){ if(i==(*it).second){ i=(*it).first; int cury = stmax.query((*it).first,(*it).second); if(cury>curr){ mx=i; curr=cury; mxy=cury; } continue; } if(y[i]>curr){ mx=i; curr=y[i]; mxy=y[i]; } curr*=x[i]; if(curr>1e9){ break; } } return (st.query(0,mx)*mxy)%mod; } int init(int N, int X[], int Y[]) { x=X; y=Y; n=N; st = segTree<long long>(x,n); stmax = segTreeMax<long long>(y,n); pair<int,int>rg={-1,-1}; for(int i = 0;i<n;i++){ if(x[i]==1){ if(rg.first==-1){ rg.first=i; rg.second=i; } else{ rg.second=i; } } else{ ones.insert(rg); rg={-1,-1}; } } return finans(); } int updateX(int pos, int val) { x[pos]=val; st.update(pos,val); return finans(); } int updateY(int pos, int val) { if(y[pos]==1&&val!=1){ pair<int,int>p = *(--ones.upper_bound({pos,-1})); if(p.second<pos){ ones.insert({pos,pos}); } else{ ones.erase(p); if(p.first!=pos){ ones.insert({p.first,pos-1}); } if(p.second!=pos){ ones.insert({pos+1,p.second}); } } } else if(y[pos]!=1&&val==1){ pair<int,int>p = *(--ones.upper_bound({pos,-1})); if(p.second==pos-1){ ones.erase(p); ones.insert({p.first,pos}); } else{ ones.insert({pos,pos}); } p=*(ones.upper_bound({pos,-1})); if(p.first==pos+1){ ones.erase(p); pair<int,int>p2=*(--ones.upper_bound({pos,-1})); ones.erase(p2); ones.insert({p2.first,p.second}); } } y[pos]=val; stmax.update(pos,val); return finans(); }

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

horses.cpp: In constructor 'segTree<T>::segTree(int*, int)':
horses.cpp:31:17: warning: declaration of 'x' shadows a global declaration [-Wshadow]
   31 |             int x = (int)pow(2,ceil(log2(siz)));
      |                 ^
horses.cpp:6:6: note: shadowed declaration is here
    6 | int *x;
      |      ^
horses.cpp: In constructor 'segTreeMax<T>::segTreeMax(int*, int)':
horses.cpp:93:17: warning: declaration of 'x' shadows a global declaration [-Wshadow]
   93 |             int x = (int)pow(2,ceil(log2(siz)));
      |                 ^
horses.cpp:6:6: note: shadowed declaration is here
    6 | int *x;
      |      ^
horses.cpp: In function 'int finans()':
horses.cpp:149:35: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  149 |             int cury = stmax.query((*it).first,(*it).second);
      |                        ~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
horses.cpp:163:12: warning: conversion from 'long long int' to 'double' may change value [-Wconversion]
  163 |         if(curr>1e9){
      |            ^~~~
horses.cpp:167:32: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  167 |     return (st.query(0,mx)*mxy)%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...