oj.uz

Submission #727310

# Submission time Handle Problem Language Result Execution time Memory
727310 2023-04-20T11:50:17 Z TheSahib Teams (IOI15_teams) C++17
100 / 100
 3430 ms 152304 KB 
#include "teams.h"
#include <bits/stdc++.h>

#define ll long long
#define pii pair<int, int>

using namespace std;

const int MAX = 5e5 + 5;
const int TREE_SIZE = MAX * 24;

int n;
//vector<pii> v;

int tree[TREE_SIZE], L[TREE_SIZE], R[TREE_SIZE];
int nxt = 0;
int roots[MAX];

void build(int node, int l, int r){
    if(l == r) return;
    int mid = (l + r) / 2;

    L[node] = ++nxt;
    R[node] = ++nxt;
    build(L[node], l, mid);
    build(R[node], mid + 1, r);
}

int update(int node, int l, int r, int pos){
    int id = ++nxt;
    tree[id] = tree[node] + 1;
    if(l == r) return id;
    
    L[id] = L[node];
    R[id] = R[node];

    int mid = (l + r) / 2;
    if(pos <= mid){
        L[id] = update(L[id], l, mid, pos);
    }
    else{
        R[id] = update(R[id], mid + 1, r, pos);
    }
    return id;
}

int ask(int node, int l, int r, int ql, int qr){
    if(ql > r || qr < l){
        return 0;
    }
    if(ql <= l && r <= qr){
        return tree[node];
    }
    int mid = (l + r) / 2;
    return ask(L[node], l, mid, ql, qr) + ask(R[node], mid + 1, r, ql, qr);
}

void init(int N, int A[], int B[])
{
    n = N;
    vector<int> a[n + 1];
    for (int i = 0; i < n; i++)
    {
        //v.push_back({A[i], B[i]});
        a[A[i]].push_back(B[i]);
    }
    for (int i = 1; i <= n; i++)
    {
        roots[i] = roots[i - 1];
        for(int r:a[i]){
            roots[i] = update(roots[i], 1, MAX, r);
        }
    }
}


int can(int M, int K[])
{
    sort(K, K + M);
    int s = 0;
    vector<pii> v;
    for (int i = 0; i < M; i++)
    {
        if(!v.empty() && v[v.size() - 1].first == K[i]){
            v[v.size() - 1].second += K[i];
        }
        else{
            v.push_back({K[i], K[i]});
        }
        s += K[i];
    }
    if(s > n) return false;
    vector<pii> blocks;
    for (int i = 0; i < v.size(); i++)
    {
        if(!blocks.empty()){
            blocks[blocks.size() - 1].second = v[i].first - 1;
        }
        blocks.push_back({v[i].first, 0});
    }
    blocks[blocks.size() - 1].second = n;

    vector<int> used;
    used.resize(blocks.size(), 0);

    for (int i = 0; i < v.size(); i++)
    {
        int need = v[i].second;
        for (int j = i; j < blocks.size(); j++)
        {
            int c = min(ask(roots[v[i].first], 1, MAX, blocks[j].first, blocks[j].second) - used[j], need);
            used[j] += c;
            need -= c;
            if(need == 0) break;
        }
        if(need != 0) return false;
    }
    return true;
}

Compilation message

teams.cpp: In function 'int can(int, int*)':
teams.cpp:94:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   94 |     for (int i = 0; i < v.size(); i++)
      |                     ~~^~~~~~~~~~
teams.cpp:106:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  106 |     for (int i = 0; i < v.size(); i++)
      |                     ~~^~~~~~~~~~
teams.cpp:109:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  109 |         for (int j = i; j < blocks.size(); j++)
      |                         ~~^~~~~~~~~~~~~~~

Subtask #1
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 312 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 340 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 308 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 308 KB Output is correct
14 Correct 1 ms 308 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 304 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 308 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 71 ms 30228 KB Output is correct
2 Correct 78 ms 30188 KB Output is correct
3 Correct 62 ms 30184 KB Output is correct
4 Correct 61 ms 30896 KB Output is correct
5 Correct 34 ms 28632 KB Output is correct
6 Correct 34 ms 28716 KB Output is correct
7 Correct 35 ms 28732 KB Output is correct
8 Correct 35 ms 28700 KB Output is correct
9 Correct 31 ms 28664 KB Output is correct
10 Correct 27 ms 28316 KB Output is correct
11 Correct 29 ms 28344 KB Output is correct
12 Correct 30 ms 28416 KB Output is correct
13 Correct 37 ms 29092 KB Output is correct
14 Correct 39 ms 29240 KB Output is correct
15 Correct 55 ms 29996 KB Output is correct
16 Correct 71 ms 30016 KB Output is correct
17 Correct 31 ms 28876 KB Output is correct
18 Correct 31 ms 29008 KB Output is correct

Subtask #3
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 109 ms 30624 KB Output is correct
2 Correct 115 ms 30476 KB Output is correct
3 Correct 223 ms 32512 KB Output is correct
4 Correct 61 ms 30332 KB Output is correct
5 Correct 53 ms 28944 KB Output is correct
6 Correct 53 ms 29012 KB Output is correct
7 Correct 64 ms 28912 KB Output is correct
8 Correct 55 ms 28960 KB Output is correct
9 Correct 28 ms 28612 KB Output is correct
10 Correct 31 ms 28452 KB Output is correct
11 Correct 71 ms 28600 KB Output is correct
12 Correct 1198 ms 28944 KB Output is correct
13 Correct 282 ms 29324 KB Output is correct
14 Correct 232 ms 31008 KB Output is correct
15 Correct 101 ms 30416 KB Output is correct
16 Correct 86 ms 30408 KB Output is correct
17 Correct 58 ms 29192 KB Output is correct
18 Correct 59 ms 29132 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 580 ms 150240 KB Output is correct
2 Correct 567 ms 150488 KB Output is correct
3 Correct 849 ms 152304 KB Output is correct
4 Correct 485 ms 151028 KB Output is correct
5 Correct 184 ms 142180 KB Output is correct
6 Correct 187 ms 142172 KB Output is correct
7 Correct 191 ms 142068 KB Output is correct
8 Correct 190 ms 142192 KB Output is correct
9 Correct 141 ms 142124 KB Output is correct
10 Correct 141 ms 140108 KB Output is correct
11 Correct 1747 ms 140476 KB Output is correct
12 Correct 3430 ms 141116 KB Output is correct
13 Correct 1045 ms 143432 KB Output is correct
14 Correct 908 ms 148132 KB Output is correct
15 Correct 393 ms 147456 KB Output is correct
16 Correct 410 ms 147200 KB Output is correct
17 Correct 217 ms 142308 KB Output is correct
18 Correct 195 ms 142544 KB Output is correct