Submission #491630

#TimeUsernameProblemLanguageResultExecution timeMemory
491630dorijanlendvajEmployment (JOI16_employment)C++14
100 / 100
575 ms32480 KiB
#include <bits/stdc++.h> #define x first #define y second #define pii pair<int,int> using namespace std; using ll=long long; #define pll pair<ll,ll> #define vi vector<int> #define vl vector<ll> #define pb push_back #define eb emplace_back #define all(a) begin(a),end(a) const int N=400010,MOD=1e9+7,M=1<<19; const char en='\n'; const ll LLINF=1ll<<60; int n,q,h[N],ti[N],a[N],b[N],seg[M*2+10]; void upd(int i,int x) { for (i+=M;i;i/=2) seg[i]+=x; } int ge(int l,int r,int lo=0,int hi=M,int i=1) { if (lo>=l && hi<=r) return seg[i]; if (lo>=r || hi<=l) return 0; int mid=(lo+hi)/2; return ge(l,r,lo,mid,i*2)+ge(l,r,mid,hi,i*2+1); } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cin>>n>>q; set<int> s; for (int i=0;i<n;++i) cin>>h[i],s.insert(h[i]); for (int i=0;i<q;++i) { cin>>ti[i]; if (ti[i]==1) { cin>>a[i]; s.insert(a[i]); } else { cin>>a[i]>>b[i]; s.insert(b[i]); } } vi v(all(s)); for (int i=0;i<n;++i) h[i]=lower_bound(all(v),h[i])-v.begin(); for (int i=0;i<q;++i) { if (ti[i]==1) a[i]=lower_bound(all(v),a[i])-v.begin(); else b[i]=lower_bound(all(v),b[i])-v.begin(); } for (int i=0;i<n;++i) { upd(h[i],1); if (i) upd(min(h[i],h[i-1]),-1); } for (int i=0;i<q;++i) { if (ti[i]==1) { cout<<ge(a[i],M)<<en; } else { --a[i]; upd(h[a[i]],-1); if (a[i]) upd(min(h[a[i]],h[a[i]-1]),1); if (a[i]<n-1) upd(min(h[a[i]],h[a[i]+1]),1); h[a[i]]=b[i]; upd(h[a[i]],1); if (a[i]) upd(min(h[a[i]],h[a[i]-1]),-1); if (a[i]<n-1) upd(min(h[a[i]],h[a[i]+1]),-1); } } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...