oj.uz

Submission #200985

# Submission time Handle Problem Language Result Execution time Memory
200985 2020-02-09T03:59:50 Z model_code Nekameleoni (COCI15_nekameleoni) C++17
140 / 140
 1607 ms 415152 KB 
#include <cassert>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <cstdio>

using namespace std;

#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define REP(i, n) FOR (i, 0, (n))
#define TRACE(x) cout << #x << " = " << x << endl
#define _ << " _ " <<

typedef long long llint;
typedef pair<llint, int> pli;

const int INF = 1e9;
const int MAXNODES = 262144;
const int offset = 131072;

inline bool subset(llint mask1, llint mask2) {
  return (mask1 & mask2) == mask1;
}

int n, k, q;

class tournament {
 private:
  struct node {
    int len;
    pli pref[50];
    pli suff[50];
    int ans;

    node() { ans = INF; len = 0; }
    node(int t, int v) {
      len = 1;
      pref[0] = suff[0] = pli(1LL<<v, t);
      ans = INF;
    }
  };

  node tree[MAXNODES];

  void merge(node &t, node &l, node &r) {
    int pref_len, suff_len;
    
    pref_len = 0;
    for (int i = 0; i < l.len; ++i)
      t.pref[pref_len++] = l.pref[i];
    for (int i = 0; i < r.len; ++i)
      if (pref_len == 0 || !subset(r.pref[i].first, t.pref[pref_len-1].first)) {
        t.pref[pref_len] = r.pref[i];
        if (pref_len > 0) t.pref[pref_len].first |= t.pref[pref_len-1].first;
        ++pref_len;
      }

    suff_len = 0;
    for (int i = 0; i < r.len; ++i)
      t.suff[suff_len++] = r.suff[i];
    for (int i = 0; i < l.len; ++i)
      if (suff_len == 0 || !subset(l.suff[i].first, t.suff[suff_len-1].first)) {
        t.suff[suff_len] = l.suff[i];
        if (suff_len > 0) t.suff[suff_len].first |= t.suff[suff_len-1].first;
        ++suff_len;
      }

    assert(pref_len == suff_len);
    t.len = pref_len;

    t.ans = INF;
    int pref_pos = 0;
    for (int suff_pos = l.len-1; suff_pos >= 0; --suff_pos) {
      while (pref_pos < r.len && (l.suff[suff_pos].first | r.pref[pref_pos].first) != (1LL<<k)-1)
        ++pref_pos;
      if (pref_pos < r.len) {
        llint curr_mask = l.suff[suff_pos].first | r.pref[pref_pos].first;
        if (curr_mask == (1LL<<k)-1)
          t.ans = min(t.ans, r.pref[pref_pos].second-l.suff[suff_pos].second+1);
      }
    }
    t.ans = min(t.ans, min(l.ans, r.ans));
  }


 public:
  tournament() {}

  void update(int t, int v) {
    t += offset;
    tree[t] = node(t-offset, v);
    for (t /= 2; t > 0; t /= 2)
      merge(tree[t], tree[2*t], tree[2*t+1]);
  }

  int query(void) {
    return tree[1].ans;
  }
  
};

tournament T;

int main(void) {
  scanf("%d%d%d", &n, &k, &q);

  REP (i, n) { 
    int v;
    scanf("%d", &v);
    --v;
    T.update(i, v);
  }

  REP (i, q) {
    int t;
    scanf("%d", &t);
    if (t == 1) {
      int x, v;
      scanf("%d%d", &x, &v);
      --x; --v;
      T.update(x, v);
    } else {
      int ans = T.query();
      printf("%d\n", ans == INF ? -1 : ans);
    }
  }

  return 0;
}

Compilation message

nekameleoni.cpp: In function 'int main()':
nekameleoni.cpp:105:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d", &n, &k, &q);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~
nekameleoni.cpp:109:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &v);
     ~~~~~^~~~~~~~~~
nekameleoni.cpp:116:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &t);
     ~~~~~^~~~~~~~~~
nekameleoni.cpp:119:12: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
       scanf("%d%d", &x, &v);
       ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 414 ms 414884 KB Output is correct
2 Correct 261 ms 414816 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 287 ms 414864 KB Output is correct
2 Correct 275 ms 414952 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 307 ms 414816 KB Output is correct
2 Correct 305 ms 414824 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 651 ms 414976 KB Output is correct
2 Correct 1230 ms 414968 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 938 ms 415096 KB Output is correct
2 Correct 1403 ms 414928 KB Output is correct

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1053 ms 415096 KB Output is correct
2 Correct 1333 ms 415096 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1284 ms 415068 KB Output is correct
2 Correct 1348 ms 415096 KB Output is correct

Subtask #8
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1252 ms 414972 KB Output is correct
2 Correct 1389 ms 414996 KB Output is correct

Subtask #9
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1607 ms 415072 KB Output is correct
2 Correct 1429 ms 415004 KB Output is correct

Subtask #10
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1587 ms 415152 KB Output is correct
2 Correct 1378 ms 415112 KB Output is correct