oj.uz

Submission #477508

# Submission time Handle Problem Language Result Execution time Memory
477508 2021-10-02T10:48:08 Z Neos Poklon (COCI17_poklon) C++14
140 / 140
 2158 ms 22712 KB 
#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef pair<ll, ll> ii;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<ii> vii;
typedef vector<vi> vvi;
typedef vector<vll> vvll;
typedef vector<vii> vvii;
 
#define task "btd"
#define fastIO ios::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL)
#define forw(i, l, r) for( ll i = (l) ; i < (r) ; i++ )
#define forb(i, r, l) for( ll i = (r) ; i >= (l) ; i-- )
#define sz(x) (int)x.size()
#define fi first
#define se second
#define all(x) x.begin(), x.end()
#define numBit(x) __builtin_popcount(x)
#define lb lower_bound
#define ub upper_bound
#define ar array
#define endl '\n'
 
const int dx[4] = {-1, 0, 1, 0};
const int dy[4] = {0, -1, 0, 1};
 
const int N = 5e5 + 7;
const ll inf = 0x3f3f3f3f;
const int block = 600;

int n, q, a[N], l[N], r[N], ans[N];

void sub1() {
  map<int, int> cnt;
  forw(i, 1, q + 1) {
    int ans = 0;
    cnt.clear();
    forw(j, l[i], r[i] + 1) {
      cnt[a[j]]++;
      if (cnt[a[j]] == 2) ++ans;
      if (cnt[a[j]] == 3) ans = max(0, ans - 1);
    }
    cout << ans << endl;
  }
}

struct query{
  int l, r, idx;
} queries[N];
 
bool cmp(query a, query b){
  if (a.l / block != b.l/block)
    return a.l / block < b.l / block;
  return a.r < b.r;
}
 
int cur, cnt[N];
void add(ll idx){
    ll tmp = ++ cnt[a[idx]];
    if (tmp == 2) cur ++; 
    if (tmp == 3) cur --;
}
void sub(ll idx){
    int tmp = -- cnt[a[idx]];
    if (tmp == 2) cur ++;
    if (tmp == 1) cur --;
}

void sub2() {
  sort(queries + 1, queries + 1 + q, cmp);
  ll l = 1, r = 0;
  bool inc = false, dec = false;
  for (int i = 1; i <= q; i ++){
    while (r < queries[i].r) add(++r);
    while (r > queries[i].r) sub(r--);
    while (l < queries[i].l) sub(l++);
    while (l > queries[i].l) add(--l);
    ans[queries[i].idx] = cur;
  }
 
  for (int i = 1; i <= q; i ++)
    cout << ans[i] << '\n';
} 

ii cmpres[N];
int main() {
  // fastIO;

  scanf("%d %d", &n, &q);
  forw(i, 1, n + 1) {
    scanf("%d", &a[i]);
    cmpres[i] = ii(a[i], i);
  }

  sort(cmpres + 1, cmpres + 1 + n);
  for (int i = 1, v = 0; i <= n; i ++){
    if (cmpres[i].fi != cmpres[i - 1].fi) v ++;
    a[cmpres[i].se] = v;
  }

  forw(i, 1, q + 1) {
    scanf("%d %d", &l[i], &r[i]);
    queries[i].l = l[i], queries[i].r = r[i];
    queries[i].idx = i;
  } 

  // sub2();
  if (n <= 5000 && q <= 5000) sub1();
  else sub2();
}

Compilation message

poklon.cpp: In function 'void sub2()':
poklon.cpp:78:8: warning: unused variable 'inc' [-Wunused-variable]
   78 |   bool inc = false, dec = false;
      |        ^~~
poklon.cpp:78:21: warning: unused variable 'dec' [-Wunused-variable]
   78 |   bool inc = false, dec = false;
      |                     ^~~
poklon.cpp: In function 'int main()':
poklon.cpp:95:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   95 |   scanf("%d %d", &n, &q);
      |   ~~~~~^~~~~~~~~~~~~~~~~
poklon.cpp:97:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   97 |     scanf("%d", &a[i]);
      |     ~~~~~^~~~~~~~~~~~~
poklon.cpp:108:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  108 |     scanf("%d %d", &l[i], &r[i]);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
140.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 7 ms 332 KB Output is correct
3 Correct 44 ms 332 KB Output is correct
4 Correct 575 ms 524 KB Output is correct
5 Correct 191 ms 4812 KB Output is correct
6 Correct 196 ms 4860 KB Output is correct
7 Correct 522 ms 9332 KB Output is correct
8 Correct 964 ms 13752 KB Output is correct
9 Correct 1496 ms 18308 KB Output is correct
10 Correct 2158 ms 22712 KB Output is correct