Submission #610899

#TimeUsernameProblemLanguageResultExecution timeMemory
610899racsosabePoklon (COCI17_poklon)C++14
140 / 140
1026 ms30636 KiB
#include<bits/stdc++.h> using namespace::std; const int N = 500000 + 5; const int SQRT = 710; const int bsize = 710; int n; int q; int a[N]; int L[N]; int val[N]; int block[SQRT]; int ans[N]; int last1[N]; int last2[N]; int last3[N]; vector<int> Q[N]; void compress(){ set<int> S; for(int i = 1; i <= n; i++) S.emplace(a[i]); int len = 0; map<int, int> id; for(int x : S){ id[x] = len++; } for(int i = 1; i <= n; i++) a[i] = id[a[i]]; } void update(int x, int y){ int idx = x / bsize; block[idx] += y; val[x] += y; } int query(int l, int r){ int res = 0; while(l % bsize and l <= r){ res += val[l]; l++; } while(l + bsize - 1 <= r){ res += block[l / bsize]; l += bsize; } while(l <= r){ res += val[l]; l++; } return res; } int get_sum(int pos){ return query(1, pos); } void fix(int i){ int x = a[i]; int l1 = last1[x], l2 = last2[x], l3 = last3[x]; if(l2){ update(l3 + 1, -1); update(l2 + 1, 1); } if(l1){ update(l2 + 1, 1); update(l1 + 1, -1); } last3[x] = l2; last2[x] = l1; last1[x] = i; } void download(int i){ for(int at : Q[i]){ ans[at] = get_sum(L[at]); } } void solve(){ for(int i = 1; i <= n; i++){ fix(i); download(i); } } int main(){ scanf("%d %d", &n, &q); for(int i = 1; i <= n; i++) scanf("%d", a + i); compress(); for(int i = 1; i <= q; i++){ int r; scanf("%d %d", L + i, &r); Q[r].emplace_back(i); } solve(); for(int i = 1; i <= q; i++) printf("%d\n", ans[i]); return 0; }

Compilation message (stderr)

poklon.cpp: In function 'int main()':
poklon.cpp:88:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   88 |  scanf("%d %d", &n, &q);
      |  ~~~~~^~~~~~~~~~~~~~~~~
poklon.cpp:89:35: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   89 |  for(int i = 1; i <= n; i++) scanf("%d", a + i);
      |                              ~~~~~^~~~~~~~~~~~~
poklon.cpp:93:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   93 |   scanf("%d %d", L + i, &r);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...