oj.uz

답안 #315435

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
315435 2020-10-22T22:27:15 Z VROOM_VARUN 코끼리 (Dancing Elephants) (IOI11_elephants) C++14
50 / 100
 2875 ms 6848 KB 
/*
ID: varunra2
LANG: C++
TASK: elephants
*/
// cp ~/SNIPPETS/Template/testing/*
// gen.cpp and build with IORun
// create brute.cpp and build with IORun
// this runs 5 random tests against a with checkts against brute
// ./test.sh 5 a
// any failed tests will be saved under data/failed*{inp,out,oac} pattern. .oac
// is output of brute, .out is output of program, .inp is output of gen

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

#ifdef DEBUG
#include "lib/debug.h"
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#define debug_arr(...) \
  cerr << "[" << #__VA_ARGS__ << "]:", debug_arr(__VA_ARGS__)
#pragma GCC diagnostic ignored "-Wsign-compare"
//#pragma GCC diagnostic ignored "-Wunused-parameter"
//#pragma GCC diagnostic ignored "-Wunused-variable"
#else
#define debug(...) 42
#endif

#define EPS 1e-9
#define IN(A, B, C) assert(B <= A && A <= C)
#define INF (int)1e9
#define MEM(a, b) memset(a, (b), sizeof(a))
#define MOD 1000000007
#define MP make_pair
#define PB push_back
#define all(cont) cont.begin(), cont.end()
#define rall(cont) cont.end(), cont.begin()
#define x first
#define y second

const double PI = acos(-1.0);
typedef long long ll;
typedef long double ld;
typedef pair<int, int> PII;
typedef map<int, int> MPII;
typedef multiset<int> MSETI;
typedef set<int> SETI;
typedef set<string> SETS;
typedef vector<int> VI;
typedef vector<PII> VII;
typedef vector<VI> VVI;
typedef vector<string> VS;

#define rep(i, a, b) for (int i = a; i < (b); ++i)
#define trav(a, x) for (auto& a : x)
#define sz(x) (int)(x).size()
typedef pair<int, int> pii;
typedef vector<int> vi;
#pragma GCC diagnostic ignored "-Wsign-compare"
// util functions

int n, l;
const int BLOCK = 400;

multiset<PII> st;
VI vals;

struct block {
  VI pnts;
  int siz;

  VI dp1;  // how many blocks for suffix starting at i, ending at pnts.size()?
  VI dp2;  // where does the optimal solution held at dp1[i] end?

  void init() {
    sort(all(pnts));
    siz = sz(pnts);
    dp1.resize(siz);
    dp2.resize(siz);
  }

  void calc() {
    init();
    int p1 = siz - 1;
    for (int i = siz - 1; i >= 0; i--) {
      while ((pnts[p1] - pnts[i]) > l) p1--;
      if (p1 == siz - 1) {
        dp1[i] = 1;
        dp2[i] = pnts[i] + l;
      } else {
        dp1[i] = dp1[p1 + 1] + 1;
        dp2[i] = dp2[p1 + 1];
      }
    }
  }

  void ins(int x) {
    pnts.PB(x);
    calc();
  }

  void del(int x) {
    VI cop;
    trav(xx, pnts) {
      if (xx == x) continue;
      cop.PB(xx);
    }
    pnts = cop;
    calc();
  }

  PII get(int x) {
    // how many to cover rest of this block starting at x
    // where would it end at
    auto it = upper_bound(all(pnts), x);
    if (it == pnts.end()) {
      return MP(0, x);
    }
    int ind = it - pnts.begin();
    return MP(dp1[ind], dp2[ind]);
  }

  void pr(int i = -1) {
    debug("printing block", i);
    debug("pnts", pnts);
    debug("dp1", dp1);
    debug("dp2", dp2);
  }
};

vector<block> blocks;

void rebuild(bool done = true) {
  // we are rebuilding blocks
  VI pnts;

  pnts = vals;

  blocks.clear();
  sort(all(pnts));
  VI cur;

  st.clear();

  for (int i = 0; i < sz(pnts); i++) {
    cur.PB(pnts[i]);
    st.insert(MP(pnts[i], sz(blocks)));
    if (sz(cur) == BLOCK) {
      block nw;
      nw.pnts = cur;
      nw.calc();
      cur.clear();
      blocks.PB(nw);
    }
  }
  if (!cur.empty()) {
    block nw;
    nw.pnts = cur;
    nw.calc();
    cur.clear();
    blocks.PB(nw);
  }
}

void ins(int x) {
  debug("we got an insertation - reeeeeeeeeeeeeeeeeee");
  debug(x);
  // what block are we in?
  auto it = st.lower_bound(MP(x, -1));
  if(it == st.end()) {
    int ind = sz(blocks) - 1;
    blocks[ind].ins(x);
    st.insert(MP(x, ind));
    return;
  }
  auto xx = *it;
  blocks[xx.y].ins(x);
  st.insert(MP(x, xx.y));
  debug(st);
  debug(xx);
}

void del(int x) {
  debug("we got a deletion - wooooooooooooooooooooooo");
  debug(x);
  auto xx = *st.lower_bound(MP(x, -1));
  blocks[xx.y].del(x);
  st.erase(st.lower_bound(MP(x, -1)));
  debug(st);
}

int qry() {
  debug("we got a query - uh oh");
  int ret = 0;
  int ind = -1;
  for (int i = 0; i < sz(blocks); i++) {
    auto x = blocks[i].get(ind);
    ret += x.x;
    ind = x.y;
    debug(ret, ind);
  }
  return ret;
}

void init(int N, int L, int X[]) {
  n = N;
  l = L;
  for (int i = 0; i < n; i++) {
    vals.PB(X[i]);
  }
  rebuild(false);  // first time building
}

int cnt = 0;

int update(int i, int y) {
  debug("we got an update asdfasfsdfasfasdfasfsadfasdfa");
  int cur = vals[i];
  vals[i] = y;
  debug(vals);
  del(cur);
  ins(y);
  cnt++;
  if (cnt % BLOCK == 0) {
    rebuild();
  }
  return qry();
}

// int main() {
// #ifndef ONLINE_JUDGE
//   freopen("elephants.in", "r", stdin);
//   freopen("elephants.out", "w", stdout);
// #endif
//   cin.sync_with_stdio(0);
//   cin.tie(0);

//   string barrier =
//       "=======================================================================";
//   debug(barrier);

//   int n, l, q;

//   cin >> n >> l >> q;

//   int x[n];

//   for (int i = 0; i < n; i++) {
//     cin >> x[i];
//   }

//   init(n, l, x);

//   debug(qry());

//   while (q--) {
//     int i, y;
//     cin >> i >> y;
//     debug(i, y);
//     int correct;
//     cin >> correct;
//     int ret = update(i, y);
//     debug(ret);
//     debug(correct);
//     debug(ret == correct);
//     assert(ret == correct);
//   }

//   return 0;
// }

Compilation message

elephants.cpp: In member function 'void block::pr(int)':
elephants.cpp:26:20: warning: statement has no effect [-Wunused-value]
   26 | #define debug(...) 42
      |                    ^~
elephants.cpp:124:5: note: in expansion of macro 'debug'
  124 |     debug("printing block", i);
      |     ^~~~~
elephants.cpp:26:20: warning: statement has no effect [-Wunused-value]
   26 | #define debug(...) 42
      |                    ^~
elephants.cpp:125:5: note: in expansion of macro 'debug'
  125 |     debug("pnts", pnts);
      |     ^~~~~
elephants.cpp:26:20: warning: statement has no effect [-Wunused-value]
   26 | #define debug(...) 42
      |                    ^~
elephants.cpp:126:5: note: in expansion of macro 'debug'
  126 |     debug("dp1", dp1);
      |     ^~~~~
elephants.cpp:26:20: warning: statement has no effect [-Wunused-value]
   26 | #define debug(...) 42
      |                    ^~
elephants.cpp:127:5: note: in expansion of macro 'debug'
  127 |     debug("dp2", dp2);
      |     ^~~~~
elephants.cpp: In function 'void ins(int)':
elephants.cpp:26:20: warning: statement has no effect [-Wunused-value]
   26 | #define debug(...) 42
      |                    ^~
elephants.cpp:166:3: note: in expansion of macro 'debug'
  166 |   debug("we got an insertation - reeeeeeeeeeeeeeeeeee");
      |   ^~~~~
elephants.cpp:26:20: warning: statement has no effect [-Wunused-value]
   26 | #define debug(...) 42
      |                    ^~
elephants.cpp:167:3: note: in expansion of macro 'debug'
  167 |   debug(x);
      |   ^~~~~
elephants.cpp:26:20: warning: statement has no effect [-Wunused-value]
   26 | #define debug(...) 42
      |                    ^~
elephants.cpp:179:3: note: in expansion of macro 'debug'
  179 |   debug(st);
      |   ^~~~~
elephants.cpp:26:20: warning: statement has no effect [-Wunused-value]
   26 | #define debug(...) 42
      |                    ^~
elephants.cpp:180:3: note: in expansion of macro 'debug'
  180 |   debug(xx);
      |   ^~~~~
elephants.cpp: In function 'void del(int)':
elephants.cpp:26:20: warning: statement has no effect [-Wunused-value]
   26 | #define debug(...) 42
      |                    ^~
elephants.cpp:184:3: note: in expansion of macro 'debug'
  184 |   debug("we got a deletion - wooooooooooooooooooooooo");
      |   ^~~~~
elephants.cpp:26:20: warning: statement has no effect [-Wunused-value]
   26 | #define debug(...) 42
      |                    ^~
elephants.cpp:185:3: note: in expansion of macro 'debug'
  185 |   debug(x);
      |   ^~~~~
elephants.cpp:26:20: warning: statement has no effect [-Wunused-value]
   26 | #define debug(...) 42
      |                    ^~
elephants.cpp:189:3: note: in expansion of macro 'debug'
  189 |   debug(st);
      |   ^~~~~
elephants.cpp: In function 'int qry()':
elephants.cpp:26:20: warning: statement has no effect [-Wunused-value]
   26 | #define debug(...) 42
      |                    ^~
elephants.cpp:193:3: note: in expansion of macro 'debug'
  193 |   debug("we got a query - uh oh");
      |   ^~~~~
elephants.cpp:26:20: warning: statement has no effect [-Wunused-value]
   26 | #define debug(...) 42
      |                    ^~
elephants.cpp:200:5: note: in expansion of macro 'debug'
  200 |     debug(ret, ind);
      |     ^~~~~
elephants.cpp: In function 'int update(int, int)':
elephants.cpp:26:20: warning: statement has no effect [-Wunused-value]
   26 | #define debug(...) 42
      |                    ^~
elephants.cpp:217:3: note: in expansion of macro 'debug'
  217 |   debug("we got an update asdfasfsdfasfasdfasfsadfasdfa");
      |   ^~~~~
elephants.cpp:26:20: warning: statement has no effect [-Wunused-value]
   26 | #define debug(...) 42
      |                    ^~
elephants.cpp:220:3: note: in expansion of macro 'debug'
  220 |   debug(vals);
      |   ^~~~~

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct

Subtask #2
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct

Subtask #3
24.0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1717 ms 2040 KB Output is correct
8 Correct 1756 ms 3376 KB Output is correct
9 Correct 2252 ms 6188 KB Output is correct
10 Correct 2089 ms 6004 KB Output is correct
11 Correct 2073 ms 5808 KB Output is correct
12 Correct 2875 ms 6848 KB Output is correct
13 Correct 2093 ms 5660 KB Output is correct

Subtask #4
0 / 47.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1717 ms 2040 KB Output is correct
8 Correct 1756 ms 3376 KB Output is correct
9 Correct 2252 ms 6188 KB Output is correct
10 Correct 2089 ms 6004 KB Output is correct
11 Correct 2073 ms 5808 KB Output is correct
12 Correct 2875 ms 6848 KB Output is correct
13 Correct 2093 ms 5660 KB Output is correct
14 Incorrect 744 ms 4216 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #5
0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1717 ms 2040 KB Output is correct
8 Correct 1756 ms 3376 KB Output is correct
9 Correct 2252 ms 6188 KB Output is correct
10 Correct 2089 ms 6004 KB Output is correct
11 Correct 2073 ms 5808 KB Output is correct
12 Correct 2875 ms 6848 KB Output is correct
13 Correct 2093 ms 5660 KB Output is correct
14 Incorrect 744 ms 4216 KB Output isn't correct
15 Halted 0 ms 0 KB -