Submission #590289

#	Time	Username	Problem	Language	Result	Execution time	Memory
590289		AlperenT	Teams (IOI15_teams)	C++17	13 / 100	4073 ms	64180 KiB

teams

#include <bits/stdc++.h>
#include "teams.h"

using namespace std;

const int N = 5e5 + 5, K = 800, INF = 1e9 + 5;
int B_SIZE, B_CNT;

int n, blockmin[N], blockmax[N];

pair<int, int> arr[N];

vector<pair<int, int>> block[N];

struct Fenwick{
    int tree[K];
    vector<pair<int, int>> hist;

    int getsum(int r){
        int sum = 0;
        for(int i = r + 1; i > 0; i -= i & -i) sum += tree[i];
        return sum;
    }

    int query(int pos){
        return getsum(pos) - getsum(pos - 1);
    }

    void update(int pos, int val, bool keephist = true){
        if(keephist) hist.push_back({pos, val});

        for(int i = pos + 1; i < K; i += i & -i) tree[i] += val;
    }

    void clearhist(){
        for(int i = (int)hist.size() - 1; i >= 0; i--) update(hist[i].first, -hist[i].second, false);
        hist.clear();
    }
};

Fenwick fw[K];

void init(int N_, int A[], int B[]){
    n = N_;

    B_SIZE = (int)sqrt(n) + 1, B_CNT = (n + B_SIZE - 1) / B_SIZE;

    for(int i = 0; i < n; i++) arr[i] = {A[i], B[i]};

    sort(arr, arr + n);

    for(int i = 0; i < n; i++) block[i / B_SIZE].push_back({arr[i].second, arr[i].first});

    for(int i = 0; i < B_CNT; i++){
        blockmin[i] = INF, blockmax[i] = -INF;

        sort(block[i].begin(), block[i].end(), greater<pair<int, int>>());

        for(int j = 0; j < block[i].size(); j++){
            blockmin[i] = min(blockmin[i], block[i][j].second);
            blockmax[i] = max(blockmax[i], block[i][j].second);

            fw[i].update(j, 1, false);
        }
    }
}

int can(int M, int k[]){
    sort(k, k + M, greater<int>());

    for(int i = 0; i < B_CNT; i++) fw[i].clearhist();

    for(int cur = 0; cur < M; cur++){
        int rem = k[cur], ptr = B_CNT - 1;

        while(rem > 0){
            if(ptr == -1) return 0;
            else if(blockmin[ptr] <= k[cur]){
                if(blockmax[ptr] <= k[cur]){
                    int l = -1, r = block[ptr].size(), m;

                    while(r - l > 1){
                        m = l + (r - l) / 2;

                        if(block[ptr][m].first >= k[cur]) l = m;
                        else r = m;
                    }

                    int cnt = fw[ptr].getsum(l);

                    if(cnt < rem){
                        rem -= cnt;

                        fw[ptr].update(0, -cnt);

                        ptr--;

                        continue;
                    }
                }
                
                vector<pair<int, int>> v;

                for(int j = 0; j < block[ptr].size(); j++){
                    if(block[ptr][j].first >= k[cur] && block[ptr][j].second <= k[cur] && fw[ptr].query(j) > 0){
                        v.push_back({block[ptr][j].second, j});
                    }
                }

                sort(v.begin(), v.end(), greater<pair<int, int>>());

                for(int i = 0; i < v.size(); i++){
                    if(rem == 0) break;

                    fw[ptr].update(v[i].second, -1);
                    rem--;
                }
            }
            
            ptr--;
        }
    }

    return 1;
}

Compilation message (stderr)

teams.cpp: In function 'void init(int, int*, int*)':
teams.cpp:59:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |         for(int j = 0; j < block[i].size(); j++){
      |                        ~~^~~~~~~~~~~~~~~~~
teams.cpp: In function 'int can(int, int*)':
teams.cpp:80:52: warning: conversion from 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   80 |                     int l = -1, r = block[ptr].size(), m;
      |                                     ~~~~~~~~~~~~~~~^~
teams.cpp:104:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  104 |                 for(int j = 0; j < block[ptr].size(); j++){
      |                                ~~^~~~~~~~~~~~~~~~~~~
teams.cpp:112:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  112 |                 for(int i = 0; i < v.size(); i++){
      |                                ~~^~~~~~~~~~

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