oj.uz

Submission #226510

# Submission time Handle Problem Language Result Execution time Memory
226510 2020-04-24T05:18:51 Z quocnguyen1012 Poklon (COCI17_poklon) C++14
140 / 140
 2078 ms 21868 KB 
#include <bits/stdc++.h>

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define ar array

using namespace std;
typedef long long ll;
typedef pair<int, int> ii;

const int maxn = 5e5 + 5, inf = 1e9;

vector<ar<int, 3>> query;
int N, Q;
int a[maxn], cnt[maxn], res[maxn], ans = 0;
vector<int> val;

void add(int i)
{
  if(cnt[a[i]] == 2) --ans;
  cnt[a[i]]++;
  if(cnt[a[i]] == 2) ++ans;
}

void del(int i)
{
  if(cnt[a[i]] == 3) ++ans;
  cnt[a[i]]--;
  if(cnt[a[i]] == 1) --ans;
}

void answer(int l, int r)
{
  static int nl = 0, nr = 0;
  if(nl == 0){
    for(int i = l; i <= r; ++i)
      add(i);
    nl = l; nr = r;
    return;
  }
  for(int i = l; i < nl; ++i)
    add(i);
  for(int i = nl; i < l; ++i)
    del(i);
  for(int i = nr + 1; i <= r; ++i)
    add(i);
  for(int i = r + 1; i <= nr; ++i)
    del(i);
  nl = l; nr = r;
}

signed main(void)
{
  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  #ifdef LOCAL
    freopen("A.INP", "r", stdin);
    freopen("A.OUT", "w", stdout);
  #endif // LOCAL
  cin >> N >> Q; query.resize(Q);
  for(int i = 1; i <= N; ++i){
    cin >> a[i];
    val.eb(a[i]);
  }
  for(int i = 0; i < Q; ++i){
    cin >> query[i][0] >> query[i][1];
    query[i][2] = i;
  }
  sort(val.begin(), val.end()); val.erase(unique(val.begin(), val.end()), val.end());
  for(int i = 1; i <= N; ++i){
    a[i] = lower_bound(val.begin(), val.end(), a[i]) - val.begin();
  }
  int sq = sqrt(N);
  sort(query.begin(), query.end(), [&](ar<int, 3> x, ar<int, 3> y){
    if(x[0] / sq == y[0] / sq) return x[1] < y[1];
    return x[0] / sq < y[0] / sq;
  });
  for(auto & all : query){
    answer(all[0], all[1]);
    res[all[2]] = ans;
  }
  for(int i = 0; i < Q; ++i)
    cout << res[i] << '\n';
}

Subtask #1
140.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 10 ms 640 KB Output is correct
5 Correct 224 ms 4468 KB Output is correct
6 Correct 226 ms 4468 KB Output is correct
7 Correct 593 ms 8944 KB Output is correct
8 Correct 1068 ms 13316 KB Output is correct
9 Correct 1536 ms 17552 KB Output is correct
10 Correct 2078 ms 21868 KB Output is correct