제출 #67892

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
67892		funcsr	팀들 (IOI15_teams)	C++17	34 / 100	4066 ms	80636 KiB

teams

#include "teams.h"
#include <vector>
#include <cassert>
#include <algorithm>
#include <iostream>
using namespace std;
#define rep(i, n) for (int i=0; i<(n); i++)
#define all(x) x.begin(), x.end()
#define uniq(x) x.erase(unique(all(x)), x.end())
#define index(x, y) (int)(lower_bound(all(x), y)-x.begin())
#define pb push_back

//#define MAX_N (1<<19)
#define MAX_N (1<<17)
struct Node {
  int val = 0;
  Node *left = NULL, *right = NULL;
};

int query(Node *n, int a, int b, int k=0, int l=0, int r=MAX_N) {
  if (b <= l || r <= a) return 0;
  if (a <= l && r <= b) return n->val;
  int ret = 0;
  if (n->left)  ret += query(n->left, a, b, k*2+1, l, (l+r)/2);
  if (n->right) ret += query(n->right, a, b, k*2+2, (l+r)/2, r);
  return ret;
}
Node *add(Node *n, int x, int v, int k=0, int l=0, int r=MAX_N) {
  if (r-l == 1) {
    Node *ret = new Node();
    ret->val = n->val+v;
    return ret;
  }
  if (n->left == NULL) n->left = new Node();
  if (n->right == NULL) n->right = new Node();
  Node *ret = new Node();
  if (x < (l+r)/2) {
    ret->left = add(n->left, x, v, k*2+1, l, (l+r)/2);
    ret->right = n->right;
  }
  else {
    ret->left = n->left;
    ret->right = add(n->right, x, v, k*2+2, (l+r)/2, r);
  }
  ret->val = n->val+v;
  return ret;
}

int N;
vector<int> G[500010];
Node *seg[500010];

inline int count(int l, int a, int b) { return query(seg[l], a, b+1); }

void init(int NN, int A[], int B[]) {
  N = NN;
  assert(N<=1e5);
  rep(i, N) G[A[i]].pb(B[i]);
  seg[0] = new Node();
  for (int i=1; i<=N; i++) {
    seg[i] = seg[i-1];
    for (int r : G[i]) seg[i] = add(seg[i], r, +1);
  }
}

int xs[500010];
int C[500010];
int demand[500010];
int can(int MM, int K[]) {
  long long sum = 0;
  rep(i, MM) sum += K[i];
  if (sum > N) return 0;
  sort(K, K+MM);
  vector<int> xs;
  rep(i, MM) C[i] = demand[i] = 0;
  rep(i, MM) {
    if (xs.empty() || xs.back() != K[i]) xs.pb(K[i]);
    demand[xs.size()-1] += K[i];
  }
  int M = xs.size();
  //cout<<"xs={";for(int x :xs)cout<<x<<",";cout<<"}\n";

  //assert(xs.size() < 1000);
  assert(M < 450);
  rep(k, M) {
    for (int r=k; r<M; r++) {
      int rpos = r+1==xs.size()?N:(xs[r+1]-1);
      C[r] += count(xs[k], xs[r], rpos) - (k>=1?count(xs[k-1], xs[r], rpos):0);
    }
    //cout<<"C=";rep(i,xs.size())cout<<C[i]<<",";cout<<": demand="<<demand[k]<<"\n";
    for (int r=k; r<M; r++) {
      int e = min(demand[k], C[r]);
      demand[k] -= e;
      C[r] -= e;
      if (demand[k] == 0) break;
    }
    if (demand[k] > 0) return 0;
  }
  return 1;
}

컴파일 시 표준 에러 (stderr) 메시지

teams.cpp: In function 'int can(int, int*)':
teams.cpp:74:15: warning: declaration of 'xs' shadows a global declaration [-Wshadow]
   vector<int> xs;
               ^~
teams.cpp:66:5: note: shadowed declaration is here
 int xs[500010];
     ^~
teams.cpp:80:18: warning: conversion to 'int' from 'std::vector<int>::size_type {aka long unsigned int}' may alter its value [-Wconversion]
   int M = xs.size();
           ~~~~~~~^~
teams.cpp:87:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       int rpos = r+1==xs.size()?N:(xs[r+1]-1);
                  ~~~^~~~~~~~~~~

• Subtask 1: 21 / 21
• Subtask 2: 13 / 13
• Subtask 3: 0 / 43
• Subtask 4: 0 / 23