Submission #727333

#	Time	Username	Problem	Language	Result	Execution time	Memory
727333		TheSahib	Teams (IOI15_teams)	C++17	100 / 100	2941 ms	145128 KiB

teams

#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 * 20;

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) >> 1;
    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) >> 1;
    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 (stderr)

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 / 21
• Subtask 2: 13 / 13
• Subtask 3: 43 / 43
• Subtask 4: 23 / 23