Submission #172130

#TimeUsernameProblemLanguageResultExecution timeMemory
172130MvCSimple game (IZhO17_game)C++11
100 / 100
82 ms6936 KiB
#pragma GCC target("avx2") #pragma GCC optimize("O3") #pragma GCC optimize("unroll-loops") #include <bits/stdc++.h> #define rc(x) return cout<<x<<endl,0 #define pb push_back #define mkp make_pair #define in insert #define er erase #define fd find #define fr first #define sc second typedef long long ll; typedef long double ld; const ll INF=0x3f3f3f3f3f3f3f3f; const ll llinf=(1LL<<62); const int inf=(1<<30); const int nmax=1e5+50; const int lim=1e6; const int mod=1e9+7; using namespace std; int n,m,a[nmax],i,x,tp,fw[lim+5]; void upd(int i,int v) { for(;i<=lim;i+=i&(-i))fw[i]+=v; } int qry(int i) { int rs=0; for(;i>=1;i-=i&(-i))rs+=fw[i]; return rs; } void chg(int l,int r,int _) { if(a[l]>a[r]) { upd(a[r],_); upd(a[l]+1,-_); } else { upd(a[l],_); upd(a[r]+1,-_); } } int main() { //freopen("sol.in","r",stdin); //freopen("sol.out","w",stdout); //mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); ios_base::sync_with_stdio(false);cin.tie(0);cerr.tie(0);cout.tie(0); cin>>n>>m; for(i=1;i<=n;i++)cin>>a[i]; for(i=2;i<=n;i++)chg(i-1,i,1); while(m--) { cin>>tp; if(tp==1) { cin>>i>>x; if(i>1)chg(i-1,i,-1); if(i<n)chg(i,i+1,-1); a[i]=x; if(i>1)chg(i-1,i,1); if(i<n)chg(i,i+1,1); } else { cin>>x; cout<<qry(x)<<'\n'; } } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...