oj.uz

Submission #534725

# Submission time Handle Problem Language Result Execution time Memory
534725 2022-03-08T16:30:34 Z cig32 Poklon (COCI17_poklon) C++17
140 / 140
 1741 ms 22456 KB 
#include "bits/stdc++.h"
using namespace std;
const int MAXN = 2e5 + 10;
const int MOD = 1e9 + 7;
#define int long long
mt19937_64 rng((int)std::chrono::steady_clock::now().time_since_epoch().count());
int rnd(int x, int y) {
  int u = uniform_int_distribution<int>(x, y)(rng); return u;
}
int bm(int b, int p) { 
  if(p==0) return 1;
  int r = bm(b, p/2);
  if(p&1) return (((r*r) % MOD) * b) % MOD;
  return (r*r) % MOD;
}
int inv(int b) {
  return bm(b, MOD-2);
}
int f[MAXN];
int nCr(int n, int r) { 
  int ans = f[n]; ans *= inv(f[r]); ans %= MOD;
  ans *= inv(f[n-r]); ans %= MOD; return ans;
}

void precomp() { 
  f[0] = 1;
  for(int i=1; i<MAXN; i++) f[i] = (f[i-1] * i) % MOD;
}
int block;
struct query {
  int l, r;
  int ans;
  int id;
};
bool cmp(query a, query b) {
  if(a.l / block == b.l / block) return a.r < b.r;
  return a.l / block < b.l / block;
}
bool qwq(query a, query b) {
  return a.id < b.id;
}
void solve(int tc) {
  int n, q;
  cin >> n >> q;
  block = ceil(sqrt(n));
  int a[n+1];
  for(int i=1; i<=n; i++)cin >> a[i];
  unordered_map<int, int> is;
  int ono = 0;
  set<int> fuck;
  for(int i=1; i<=n; i++) fuck.insert(a[i]);
  for(int x: fuck) {
    is[x] = ++ono;
  }
  for(int i=1; i<=n; i++) a[i] = is[a[i]];
  int freq[ono + 1];
  for(int i=1; i<=ono; i++) freq[i] = 0;
  query uwu[q+1];
  for(int i=1; i<=q; i++) {
    cin >> uwu[i].l >> uwu[i].r;
    uwu[i].id = i;
  }
  sort(uwu + 1, uwu + 1 + q, cmp);
  int cur = 0;
  for(int i=uwu[1].l; i<=uwu[1].r; i++) {
    freq[a[i]]++;
    if(freq[a[i]] == 2) cur++;
    if(freq[a[i]] == 3) cur--;
  }
  uwu[1].ans = cur;
  for(int i=2; i<=q; i++) {
    while(uwu[i].l < uwu[i-1].l) {
      uwu[i-1].l--;
      freq[a[uwu[i-1].l]]++;
      if(freq[a[uwu[i-1].l]] == 2) cur++;
      if(freq[a[uwu[i-1].l]] == 3) cur--;
    }
    while(uwu[i].l > uwu[i-1].l) {
      freq[a[uwu[i-1].l]]--;
      if(freq[a[uwu[i-1].l]] == 2) cur++;
      if(freq[a[uwu[i-1].l]] == 1) cur--;
      uwu[i-1].l++;
    }
    while(uwu[i].r < uwu[i-1].r) {
      freq[a[uwu[i-1].r]]--;
      if(freq[a[uwu[i-1].r]] == 2) cur++;
      if(freq[a[uwu[i-1].r]] == 1) cur--;
      uwu[i-1].r--;
    }
    while(uwu[i].r > uwu[i-1].r) {
      uwu[i-1].r++;
      freq[a[uwu[i-1].r]]++;
      if(freq[a[uwu[i-1].r]] == 2) cur++;
      if(freq[a[uwu[i-1].r]] == 3) cur--;
    }
    uwu[i].ans = cur;
  }
  sort(uwu + 1, uwu + 1 + q, qwq);
  for(int i=1; i<=q; i++) {
    cout << uwu[i].ans << "\n";
  }
}
int32_t main(){
  precomp();
  ios::sync_with_stdio(0); cin.tie(0);
  int t = 1; //cin >> t;
  for(int i=1; i<=t; i++) solve(i);
}

Subtask #1
140.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1868 KB Output is correct
2 Correct 3 ms 1868 KB Output is correct
3 Correct 4 ms 1868 KB Output is correct
4 Correct 8 ms 2116 KB Output is correct
5 Correct 200 ms 6056 KB Output is correct
6 Correct 202 ms 6024 KB Output is correct
7 Correct 504 ms 10192 KB Output is correct
8 Correct 897 ms 14364 KB Output is correct
9 Correct 1332 ms 18416 KB Output is correct
10 Correct 1741 ms 22456 KB Output is correct