oj.uz

Submission #74293

# Submission time Handle Problem Language Result Execution time Memory
74293 2018-08-31T01:11:24 Z funcsr Teams (IOI15_teams) C++17
0 / 100
 4000 ms 411624 KB 
#include "teams.h"
#include <iostream>
#include <vector>
#include <set>
#include <queue>
#include <algorithm>
#include <cassert>
using namespace std;
#define MAX_N (1<<19)
#define rep(i, n) for (int i=0; i<(n); i++)
#define pb push_back

struct SegTree {
  SegTree *left = NULL, *right = NULL;
  int available;
  SegTree(int a) : available(a) {}

  SegTree *add(int p, int l=0, int r=MAX_N) {
    if (r-l == 1) {
      return new SegTree(available+1);
    }
    int mid = (l+r)/2;
    SegTree *new_left = left, *new_right = right;
    if (p < mid) {
      if (!left) left = new SegTree(0);
      new_left = left->add(p, l, mid);
    }
    else {
      if (!right) right = new SegTree(0);
      new_right = right->add(p, mid, r);
    }
    SegTree *ret = new SegTree(available+1);
    ret->left = new_left;
    ret->right = new_right;
    return ret;
  }
};

int used[MAX_N*2-1];
SegTree *last[MAX_N*2-1];
void setLazy(int k, SegTree *v) {
  last[k] = v;
  if (last[k] != NULL) used[k] = last[k]->available;
}
void push(int k) {
  if (last[k] == NULL) return;
  setLazy(k*2+1, last[k]->left);
  setLazy(k*2+2, last[k]->right);
  last[k] = NULL;
}
int N;
SegTree *seg[500001];

int take(SegTree *x, int a, int b, int num, int k=0, int l=0, int r=MAX_N) {
  if (x == NULL) return num;
  if (num == 0) return 0;
  if (b <= l || r <= a) return num;
  if (a <= l && r <= b) {
    int rest = x->available-used[k];
    if (rest == 0) return num;
    if (num >= rest) {
      setLazy(k, x);
      assert(used[k] == x->available);
      return num - rest;
    }
    else {
      if (r-l==1) {
        used[k] += rest;
        return num - rest;
      }
      // continue
    }
  }
  push(k);
  num = take(x->left, a, b, num, k*2+1, l, (l+r)/2);
  num = take(x->right, a, b, num, k*2+2, (l+r)/2, r);
  used[k] = used[k*2+1]+used[k*2+2];
  return num;
}

vector<int> G[500001];
void init(int NN, int A[], int B[]) {
  N=NN;
  rep(i, N) G[A[i]].pb(B[i]);
  SegTree *head = new SegTree(0);
  rep(l, N+1) {
    for (int r : G[l]) head = head->add(r);
    seg[l] = head;
  }
}

int can(int M, int K[]) {
  long long sum = 0;
  rep(i, M) sum += K[i];
  if (sum > N) return 0;
  rep(i, MAX_N*2-1) used[i] = 0, last[i] = NULL;
  sort(K, K+M);

  rep(i, M) {
    if (take(seg[K[i]], K[i], MAX_N, K[i]) > 0) return 0;
  }
  return 1;
}

Subtask #1
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 24312 KB Output is correct
2 Correct 21 ms 24444 KB Output is correct
3 Correct 293 ms 24648 KB Output is correct
4 Correct 292 ms 24668 KB Output is correct
5 Correct 300 ms 24668 KB Output is correct
6 Correct 15 ms 24668 KB Output is correct
7 Correct 294 ms 24980 KB Output is correct
8 Correct 295 ms 24980 KB Output is correct
9 Correct 295 ms 24980 KB Output is correct
10 Incorrect 295 ms 24980 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #2
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 184 ms 96164 KB Output is correct
2 Correct 196 ms 97408 KB Output is correct
3 Correct 184 ms 98516 KB Output is correct
4 Correct 191 ms 100304 KB Output is correct
5 Correct 127 ms 100304 KB Output is correct
6 Correct 128 ms 100304 KB Output is correct
7 Correct 133 ms 100304 KB Output is correct
8 Correct 138 ms 100304 KB Output is correct
9 Incorrect 128 ms 100304 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #3
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 792 ms 105888 KB Output is correct
2 Correct 935 ms 107420 KB Output is correct
3 Execution timed out 4048 ms 108560 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1619 ms 398120 KB Output is correct
2 Correct 1713 ms 405608 KB Output is correct
3 Execution timed out 4066 ms 411624 KB Time limit exceeded
4 Halted 0 ms 0 KB -