oj.uz

Submission #959360

# Submission time Handle Problem Language Result Execution time Memory
959360 2024-04-08T05:54:09 Z Spade1 Martian DNA (BOI18_dna) C++14
0 / 100
 25 ms 4568 KB 
#pragma once
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef double db;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<ld, ld> pld;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<ld> vld;
typedef vector<pii> vpii;
typedef vector<pll> vpll;
typedef vector<pld> vpld;
typedef vector<vi> vvi;

template<typename T> using pq = priority_queue<T>;
template<typename T> using pqg = priority_queue<T, vector<T>, greater<T>>;

#define rep0(a) for (int i = 0; i < a; ++i)
#define rep1(i, a) for (int i = 0; i < a; ++i)
#define rep2(i, a, b) for (int i = a; i <= b; ++i)
#define rep3(i, a, b, c) for (int i = a; i <= b; i+=c) 
#define overload4(a, b, c, d, e, ...) e
#define rep(...) overload4(__VA_ARGS__, rep3, rep2, rep1, rep0)(__VA_ARGS__)
#define repd0(a) for (int i = a; i >= 1; --i)
#define repd1(i, a) for (int i = a; i >= 1; --i)
#define repd2(i, a, b) for (int i = b; i >= a; --i)
#define repd3(i, a, b, c) for (int i = b; i >= a; i-=c)
#define repd(...) overload4(__VA_ARGS__, repd3, repd2, repd1, repd0)(__VA_ARGS__)
#define trav(a, x) for (auto& a : x)

#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define st first
#define nd second
#define lb lower_bound
#define ub upper_bound
#define all(x) (x).begin(), (x).end()
#define ins insert

template<typename T> bool ckmin(T &a, const T &b) { return b < a ? a = b, 1 : 0; }
template<typename T> bool ckmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; }

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int MOD = 1e9 + 7;
const int INF = 0x3fffffff;
const ll LINF = 0x1fffffffffffffff;
const char nl = '\n';
const int MX = 1e5 + 3;

void solve() {
  int n, k, r; cin >> n >> k >> r;
  vi a(n+1), ask(k, 0), cur(k+1, 0); rep(i, 1, n) cin >> a[i];
  int ans = INF, cnt = 0, idx = 1;
  rep(i, 1, r) {
    int b, q; cin >> b >> q;
    ask[b] = q;
  }
  rep(i, 1, n) {
    while (idx < n && cnt != r) {
      int now = a[idx];
      cur[now]++; 
      if (cur[now] == ask[now]) cnt++;
      idx++;
    }
    if (cnt == r) ckmin(ans, idx-i);
    int now = a[i];
    if (cur[now] == ask[now]) cnt--;  
    cur[now]--;
  }
  cout << (ans == INF ? "impossible" : to_string(ans)) << nl;
}

int main(int argc, char* argv[]) {
  ios_base::sync_with_stdio(0); cin.tie(NULL);
  int t = 1;
  // cin >> t;
  while (t--) { solve(); }
  return 0;
}

Compilation message

dna.cpp:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~

Subtask #1
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Incorrect 0 ms 460 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Incorrect 0 ms 348 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #3
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 1628 KB Output is correct
2 Correct 10 ms 1492 KB Output is correct
3 Correct 11 ms 1628 KB Output is correct
4 Correct 11 ms 1628 KB Output is correct
5 Correct 14 ms 2904 KB Output is correct
6 Incorrect 9 ms 1628 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 3652 KB Output is correct
2 Correct 20 ms 3372 KB Output is correct
3 Correct 19 ms 2908 KB Output is correct
4 Correct 11 ms 1628 KB Output is correct
5 Correct 23 ms 4180 KB Output is correct
6 Correct 25 ms 4568 KB Output is correct
7 Correct 12 ms 2140 KB Output is correct
8 Correct 15 ms 2396 KB Output is correct
9 Correct 9 ms 1628 KB Output is correct
10 Correct 10 ms 1628 KB Output is correct
11 Correct 11 ms 1620 KB Output is correct
12 Correct 10 ms 1628 KB Output is correct
13 Correct 13 ms 2772 KB Output is correct
14 Incorrect 9 ms 1628 KB Output isn't correct
15 Halted 0 ms 0 KB -