oj.uz

Submission #561947

# Submission time Handle Problem Language Result Execution time Memory
561947 2022-05-13T20:18:08 Z tae826 Teams (IOI15_teams) C++17
100 / 100
 3749 ms 389184 KB 
#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

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.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 0 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 1 ms 340 KB Output is correct
21 Correct 1 ms 340 KB Output is correct
22 Correct 1 ms 340 KB Output is correct
23 Correct 1 ms 340 KB Output is correct
24 Correct 1 ms 340 KB Output is correct
25 Correct 1 ms 340 KB Output is correct
26 Correct 1 ms 340 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 143 ms 67584 KB Output is correct
2 Correct 127 ms 67592 KB Output is correct
3 Correct 119 ms 67616 KB Output is correct
4 Correct 141 ms 68456 KB Output is correct
5 Correct 94 ms 62448 KB Output is correct
6 Correct 84 ms 62360 KB Output is correct
7 Correct 87 ms 62496 KB Output is correct
8 Correct 93 ms 62524 KB Output is correct
9 Correct 103 ms 63564 KB Output is correct
10 Correct 78 ms 63528 KB Output is correct
11 Correct 80 ms 63400 KB Output is correct
12 Correct 80 ms 63308 KB Output is correct
13 Correct 103 ms 63408 KB Output is correct
14 Correct 100 ms 66176 KB Output is correct
15 Correct 113 ms 67100 KB Output is correct
16 Correct 121 ms 67252 KB Output is correct
17 Correct 123 ms 64076 KB Output is correct
18 Correct 90 ms 64020 KB Output is correct

Subtask #3
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 533 ms 68044 KB Output is correct
2 Correct 458 ms 69684 KB Output is correct
3 Correct 233 ms 73308 KB Output is correct
4 Correct 125 ms 69680 KB Output is correct
5 Correct 156 ms 63900 KB Output is correct
6 Correct 208 ms 63872 KB Output is correct
7 Correct 165 ms 64040 KB Output is correct
8 Correct 220 ms 64100 KB Output is correct
9 Correct 81 ms 64540 KB Output is correct
10 Correct 91 ms 64460 KB Output is correct
11 Correct 88 ms 64588 KB Output is correct
12 Correct 975 ms 64936 KB Output is correct
13 Correct 285 ms 65368 KB Output is correct
14 Correct 268 ms 71268 KB Output is correct
15 Correct 150 ms 69140 KB Output is correct
16 Correct 180 ms 69204 KB Output is correct
17 Correct 142 ms 65924 KB Output is correct
18 Correct 120 ms 66036 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2693 ms 373512 KB Output is correct
2 Correct 3749 ms 380668 KB Output is correct
3 Correct 1193 ms 389184 KB Output is correct
4 Correct 865 ms 380888 KB Output is correct
5 Correct 684 ms 351436 KB Output is correct
6 Correct 981 ms 351464 KB Output is correct
7 Correct 705 ms 351556 KB Output is correct
8 Correct 1026 ms 351460 KB Output is correct
9 Correct 458 ms 352632 KB Output is correct
10 Correct 445 ms 350632 KB Output is correct
11 Correct 1726 ms 351144 KB Output is correct
12 Correct 2820 ms 352236 KB Output is correct
13 Correct 1309 ms 356736 KB Output is correct
14 Correct 1205 ms 382752 KB Output is correct
15 Correct 796 ms 375788 KB Output is correct
16 Correct 886 ms 375860 KB Output is correct
17 Correct 576 ms 357780 KB Output is correct
18 Correct 582 ms 357780 KB Output is correct