Submission #623505

#	Time	Username	Problem	Language	Result	Execution time	Memory
623505		BalintR	Teams (IOI15_teams)	C++17	100 / 100	1544 ms	126820 KiB

teams

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

typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
#define pb push_back
#define fs first
#define sn second

const int MN = 5e5 + 5, TREE_SZ = 1 << 20;
int n, q;
pii arr[MN];
int mem[10 << 20], tree[TREE_SZ], vecSz[TREE_SZ], sumDec[TREE_SZ], lastRem[TREE_SZ];
vi needReset;
int t, l, v;
const int r = TREE_SZ >> 1;

void update(int i, int segL, int segR, int prvLast){
    if(r <= segL || l >= segR || v == 0) return;
    needReset.pb(i);
    if(prvLast > lastRem[i]) sumDec[i] = 0;
    lastRem[i] = prvLast = max(lastRem[i], prvLast);

    if(l <= segL){
        int gv = upper_bound(mem + tree[i],mem + tree[i] + vecSz[i], t) - upper_bound(mem + tree[i], mem + tree[i] + vecSz[i], lastRem[i]) - sumDec[i];
        if(gv <= v){
            sumDec[i] = 0;
            lastRem[i] = t;
            v -= gv;
            return;
        }
    }
    if(segL + 1 == segR){
        sumDec[i] += v;
        v = 0;
        return;
    }

    int mid = (segL + segR) >> 1;
    int oldV = v;
    update(i * 2, segL, mid, prvLast);
    sumDec[i] += oldV - v;
    if(v == 0) return;
    oldV = v;
    update(i * 2 + 1, mid, segR, prvLast);
    sumDec[i] += oldV - v;
}

void init(int N, int *A, int *B){
    n = N;
    for (int i = 0; i < n; ++i) {
        arr[i] = {A[i], B[i]};
        for(int j = r + B[i]; j; j >>= 1) vecSz[j]++;
    }
    sort(arr, arr + n);

    for (int i = 1; i < TREE_SZ; ++i) {
        tree[i] = tree[i-1] + vecSz[i-1];
        vecSz[i-1] = 0;
    }
    for (int i = 0; i < n; ++i) {
        for(int j = r + arr[i].sn; j; j >>= 1){
            mem[tree[j] + vecSz[j]++] = arr[i].fs;
        }
    }
}

int can(int k, int *reqSizes){
    ll sum = 0;
    for (int i = 0; i < k; ++i) sum += reqSizes[i];
    if(sum > n) return 0;
    sort(reqSizes, reqSizes + k);

    bool works = true;
    for (int i = 0; i < k; ++i) {
        t = l = v = reqSizes[i];
        update(1, 0, r, 0);
        if(v){
            works = false;
            break;
        }
    }

    for(int ind : needReset) sumDec[ind] = lastRem[ind] = 0;
    needReset.clear();
    return works;
}

Compilation message (stderr)

teams.cpp: In function 'void update(int, int, int, int)':
teams.cpp:27:140: warning: conversion from 'long int' to 'int' may change value [-Wconversion]
   27 |         int gv = upper_bound(mem + tree[i],mem + tree[i] + vecSz[i], t) - upper_bound(mem + tree[i], mem + tree[i] + vecSz[i], lastRem[i]) - sumDec[i];
      |                  ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~

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