Submission #643407

#	Time	Username	Problem	Language	Result	Execution time	Memory
643407		devariaota	Martian DNA (BOI18_dna)	C++17	100 / 100	237 ms	20844 KiB

dna

#include <bits/stdc++.h>
using namespace std;

#define nyahalo ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define otsumiko exit(0);
#define mikodanye priority_queue<pair<long long, long long>, vector<pair<long long, long long> >, greater<pair<long long, long long> > >
#define mikochi priority_queue<long long, vector<long long>, greater<long long> >

long long n, k, rh, a[200069], sg[800069], l, r, x, mx = 1e10, ans, cn, ci, ln, cl, cr, b, q, sz, pn, rq[200069], sp[200069], pq, pv, cv, lz[800069], ca;
vector<long long> pos[200069];
vector<pair<long long, long long> > vc;

void prop(long long v, long long sl, long long sr) {
  if (lz[v] != 0) {
    sg[v] += lz[v];
    sg[v] = min(sg[v], mx);
    if (sl != sr) {
      lz[2*v] += lz[v];
      lz[2*v+1] += lz[v];
    }
    lz[v] = 0;
  }
}

void upd(long long v, long long sl, long long sr) {
  if (l>r) {
    return;
  }
  prop(v, sl, sr);
  if (sl>r || sr<l) {
    return;
  }
  if (sl>=l && sr<=r) {
    lz[v] += x;
    prop(v, sl, sr);
    return;
  }
  long long md = (sl+sr)/2;
  upd(2*v, sl, md);
  upd(2*v+1, md+1, sr);
  sg[v] = max(sg[2*v], sg[2*v+1]);
  sg[v] = min(sg[v], mx);
}

long long qr(long long v, long long sl, long long sr) {
  if (l>r) {
    return 0;
  }
  prop(v, sl, sr);
  if (sl>r | sr<l) {
    return 0;
  }
  if (sl>=l && sr<=r) {
    return sg[v];
  }
  long long md = (sl+sr)/2, cn, nn1, nn2;
  nn1 = qr(2*v, sl, md);
  nn2 = qr(2*v, md+1, sr);
  cn = max(nn1, nn2);
  cn = min(cn, mx);
  return cn;
}

int main() {
  nyahalo
  long long i, j;
  ans = mx;
  cin >> n >> k >> rh;
  for (i=1; i<=k; i++) {
    rq[i] = 0;
  }
  for (i=1; i<=n; i++) {
    cin >> a[i];
    pos[a[i]].push_back(i);
  }
  for (i=1; i<=rh; i++) {
    cin >> b >> q;
    vc.push_back(make_pair(b, q));
    rq[b] = q;
  }
  sort(vc.begin(), vc.end());
  sz = vc.size();
  for (i=0; i<sz; i++) {
    l = i+1;
    r = i+1;
    b = vc[i].first;
    q = vc[i].second;
    if (pos[b].size()<q) {
      x = mx;
    } else {
      cl = pos[b][0];
      cr = pos[b][q-1];
      x = cr;
    }
    sp[b] = i+1;
    upd(1, 1, sz);
  }
  for (i=1; i<=n; i++) {
    if (i == 1) {
      l = 1;
      r = sz;
      ca = qr(1, 1, sz);
      //cout << "ca: " << ca << "\n";
      ans = min(ans, ca);
      continue;
    }
    pn = a[i-1];
    pq = rq[pn];
    if (pq>0) {
      //cout << "i: " << i << "\n";
      cl = lower_bound(pos[pn].begin(), pos[pn].end(), i-1)-pos[pn].begin();
      cr = cl+pq-1;
      //cout << "cl: " << cl << " cr: " << cr << "\n";
      if (cr>=pos[pn].size()) {
        x = mx;
      } else {
        pv = pos[pn][cr]-pos[pn][cl]+1;
        cl++;
        cr++;
        if (cr>=pos[pn].size()) {
          cv = mx+pv;
        } else {
          cv = pos[pn][cr]-i+1;
        }
        x = cv-pv;
      }
      ci = sp[pn];
      l = ci;
      r = ci;
      upd(1, 1, sz);
      l = 1;
      r = ci-1;
      x = -1;
      upd(1, 1, sz);
      l = ci+1;
      r = sz;
      x = -1;
      upd(1, 1, sz);
    } else {
      l = 1;
      r = sz;
      x = -1;
      upd(1, 1, sz);
    }
    l = 1;
    r = sz;
    //cout << "ca: " << ca << "\n";
    ca = qr(1, 1, sz);
    ans = min(ans, ca);
  }
  if (ans>1e9) {
    cout << "impossible\n";
  } else {
    cout << ans << "\n";
  }
  otsumiko
}

Compilation message (stderr)

dna.cpp: In function 'long long int qr(long long int, long long int, long long int)':
dna.cpp:50:9: warning: suggest parentheses around comparison in operand of '|' [-Wparentheses]
   50 |   if (sl>r | sr<l) {
      |       ~~^~
dna.cpp: In function 'int main()':
dna.cpp:88:22: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   88 |     if (pos[b].size()<q) {
      |         ~~~~~~~~~~~~~^~
dna.cpp:114:13: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  114 |       if (cr>=pos[pn].size()) {
      |           ~~^~~~~~~~~~~~~~~~
dna.cpp:120:15: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  120 |         if (cr>=pos[pn].size()) {
      |             ~~^~~~~~~~~~~~~~~~
dna.cpp:66:16: warning: unused variable 'j' [-Wunused-variable]
   66 |   long long i, j;
      |                ^

• Subtask 1: 16 / 16
• Subtask 2: 24 / 24
• Subtask 3: 28 / 28
• Subtask 4: 32 / 32