Submission #561947

#	Time	Username	Problem	Language	Result	Execution time	Memory
561947		tae826	Teams (IOI15_teams)	C++17	100 / 100	3749 ms	389184 KiB

teams

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

struct data{
    int s, e;
    bool operator < (const data &r) const {
        if(e == r.e) return s < r.s;
        return e < r.e;
    }
} a[500100];

struct Node {
    int gap;
    Node *lf, *rg;
    Node() {
        gap = 0; lf = rg = NULL;
    }
} *tree[500100];

Node* add(Node* now, int s, int e, int target, int v) {
    if(now == NULL) { now = new Node(); }
    if(s > target || e < target) return now;
    if(s == e) { Node *ret = new Node(); ret->gap = now->gap + 1; return ret; }
    int m = s+e>>1;
    Node* ret = new Node();
    Node* lch = add(now->lf, s, m, target, v);
    Node* rch = add(now->rg, m+1, e, target, v);
    ret->gap = lch->gap + rch->gap; ret->lf = lch; ret->rg = rch;
    return ret;
}

int query(Node* now, int s, int e, int si, int ei){
    if(now == NULL) return 0;
    if(s > ei || e < si) return 0;
    if(s >= si && e <= ei) return now->gap;
    int m = s+e>>1;
    return query(now->lf, s, m, si, ei) + query(now->rg, m+1, e, si, ei);
}

int p[500100], q[500100], num[500100], K[500100], ptr[500100], N;
int Cnt[801][801], qQ[500100];

int Count(int xs, int xe, int ys, int ye) {
    return query(tree[xe], 1, N, ys, ye) - query(tree[xs-1], 1, N, ys, ye);
}

void init(int _N, int A[], int B[]) {
    N = _N;
    int i;
    for(i=1; i<=N; i++) a[i].s = A[i-1], a[i].e = B[i-1];
    sort(a+1, a+N+1);
    for(i=1; i<=N; i++) p[i] = a[i].s, q[i] = a[i].e;
    tree[0] = new Node();
    for(i=1; i<=N; i++) {
        tree[i] = new Node();
        tree[i]->gap = tree[i-1]->gap; tree[i]->lf = tree[i-1]->lf; tree[i]->rg = tree[i-1]->rg;
        tree[i] = add(tree[i], 1, N, p[i], 1);
    }
    for(i=1; i<=N; i++) qQ[i] = lower_bound(q+1, q+N+1, i) - q;
}

int can(int M, int k[]) {
    int i, j;
    for(i=1; i<=M; i++) K[i] = k[i-1];
	sort(K+1, K+M+1);
    for(i=1; i<=M; i++) num[K[i]] = 0;
    for(i=1; i<=M; i++) num[K[i]] += K[i];
    M = unique(K+1, K+M+1) - K - 1;
    int now = 0, ans = 1;
    for(i=1; i<=M; i++) {
        int numHap = 0;
        ptr[i] = qQ[K[i]];
        for(j=1; j<i; j++) {
            if(num[K[j]] == 0) continue;
            int numCnt = Count(ptr[i-1], ptr[i]-1, 1, K[j]) - numHap;
            now -= min(numCnt, num[K[j]]);
            numHap += min(numCnt, num[K[j]]);
            num[K[j]] -= min(numCnt, num[K[j]]);
        }
        now += num[K[i]];
        int cnt = Count(ptr[i], N, 1, K[i]);
        if(cnt < now) ans = 0;
    }
    return ans;
}

Compilation message (stderr)

teams.cpp: In function 'Node* add(Node*, int, int, int, int)':
teams.cpp:25:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   25 |     int m = s+e>>1;
      |             ~^~
teams.cpp: In function 'int query(Node*, int, int, int, int)':
teams.cpp:37:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   37 |     int m = s+e>>1;
      |             ~^~
teams.cpp: In function 'void init(int, int*, int*)':
teams.cpp:60:60: warning: conversion from 'long int' to 'int' may change value [-Wconversion]
   60 |     for(i=1; i<=N; i++) qQ[i] = lower_bound(q+1, q+N+1, i) - q;
      |                                 ~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~
teams.cpp: In function 'int can(int, int*)':
teams.cpp:69:32: warning: conversion from 'long int' to 'int' may change value [-Wconversion]
   69 |     M = unique(K+1, K+M+1) - K - 1;
      |         ~~~~~~~~~~~~~~~~~~~~~~~^~~

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