Submission #189405

#TimeUsernameProblemLanguageResultExecution timeMemory
189405dndhkEmployment (JOI16_employment)C++14
100 / 100
1322 ms41244 KiB
#include <bits/stdc++.h> using namespace std; #define pb push_back typedef long long ll; typedef pair<int, int> pii; typedef pair<ll, ll> pll; const int MAX_N = 200000; int N, M, K; int A[MAX_N+1]; vector<int> vt; struct S{ int t, a, b; }; vector<S> query; map<int, int> mp; void input(){ scanf("%d%d", &N, &M); for(int i=1; i<=N; i++){ scanf("%d", &A[i]); vt.pb(A[i]); } for(int i=1; i<=M; i++){ int t, a, b=0; scanf("%d", &t); if(t==1){ scanf("%d", &a); vt.pb(a); }else{ scanf("%d%d", &a, &b); vt.pb(b); } query.pb({t, a, b}); } sort(vt.begin(), vt.end()); vt.erase(unique(vt.begin(), vt.end()), vt.end()); for(int i=0; i<vt.size(); i++){ mp[vt[i]] = i+1; } for(int i=1; i<=N; i++) A[i] = mp[A[i]]; for(int i=0; i<query.size(); i++){ if(query[i].t==1){ query[i].a = mp[query[i].a]; }else{ query[i].b = mp[query[i].b]; } } K = vt.size();} struct SEG{ struct NODE{ int l, r; int sum; }; int SZ; vector<NODE> seg; void add(){ seg.pb({-1, -1, 0}); } void Init(int x){ SZ = x; add(); init(0, 1, SZ); } void init(int idx, int s, int e){ if(s==e) return; seg[idx].l = seg.size(); add(); seg[idx].r = seg.size(); add(); init(seg[idx].l, s, (s+e)/2); init(seg[idx].r, (s+e)/2+1, e); } void Add(int x, int y, int z){ add(0, 1, SZ, x, y, z); } void add(int idx, int s, int e, int x, int y, int z){ if(x<=s && e<=y){ seg[idx].sum+=z; return; } if(x>e || y<s) return; add(seg[idx].l, s, (s+e)/2, x, y, z); add(seg[idx].r, (s+e)/2+1, e, x, y, z); } int Sum(int x){ return sum(0, 1, SZ, x); } int sum(int idx, int s, int e, int k){ if(s==e) return seg[idx].sum; if(k<=(s+e)/2){ return seg[idx].sum+sum(seg[idx].l, s, (s+e)/2, k); }else{ return seg[idx].sum+sum(seg[idx].r, (s+e)/2+1, e, k); } } }Seg; void add(int x, int y){ if(N==1){ Seg.Add(1, y, 1); return; } if(x==1){ if((pii){y, x} > (pii){A[x+1], x+1}){ Seg.Add(1, y, 1); } }else if(x==N){ if((pii){y, x} > (pii){A[x-1], x-1}){ Seg.Add(1, y, 1); } }else{ if((pii){y, x} > (pii){A[x-1], x-1} && (pii){y, x} > (pii){A[x+1], x+1}){ Seg.Add(1, y, 1); }else if((pii){y, x} < (pii){A[x-1], x-1} && (pii){y, x} < (pii){A[x+1], x+1}){ Seg.Add(1, y, -1); } } } void rmv(int x, int y){ if(N==1){ Seg.Add(1, y, -1); return; } if(x==1){ if((pii){y, x} > (pii){A[x+1], x+1}){ Seg.Add(1, y, -1); } }else if(x==N){ if((pii){y, x} > (pii){A[x-1], x-1}){ Seg.Add(1, y, -1); } }else{ if((pii){y, x} > (pii){A[x-1], x-1} && (pii){y, x} > (pii){A[x+1], x+1}){ Seg.Add(1, y, -1); }else if((pii){y, x} < (pii){A[x-1], x-1} && (pii){y, x} < (pii){A[x+1], x+1}){ Seg.Add(1, y, 1); } } } int main(){ input(); Seg.Init(K); for(int i=1; i<=N; i++){ add(i, A[i]); } for(int i=0; i<query.size(); i++){ int t = query[i].t, a = query[i].a, b = query[i].b; if(t==2){ rmv(a, A[a]); if(a!=1){ rmv(a-1, A[a-1]); }if(a!=N){ rmv(a+1, A[a+1]); } A[a] = b; add(a, b); if(a!=1){ add(a-1, A[a-1]); }if(a!=N){ add(a+1, A[a+1]); } }else{ printf("%d\n", Seg.Sum(a)); } } return 0; }

Compilation message (stderr)

employment.cpp: In function 'void input()':
employment.cpp:41:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<vt.size(); i++){
               ~^~~~~~~~~~
employment.cpp:45:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<query.size(); i++){
               ~^~~~~~~~~~~~~
employment.cpp: In function 'int main()':
employment.cpp:153:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<query.size(); i++){
               ~^~~~~~~~~~~~~
employment.cpp: In function 'void input()':
employment.cpp:22:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &N, &M);
  ~~~~~^~~~~~~~~~~~~~~~
employment.cpp:24:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &A[i]);
   ~~~~~^~~~~~~~~~~~~
employment.cpp:29:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &t);
   ~~~~~^~~~~~~~~~
employment.cpp:31:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d", &a);
    ~~~~~^~~~~~~~~~
employment.cpp:34:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d%d", &a, &b);
    ~~~~~^~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...