Submission #792032

#	Time	Username	Problem	Language	Result	Execution time	Memory
792032		jasmin	Teams (IOI15_teams)	C++17	0 / 100	1070 ms	212052 KiB

teams

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

struct node{
    int left=-1;
    int right=-1;
    int val=0;
};

struct segtree{
    vector<node> tree;
    map<int, int> root;
    int mom=0;

    int build(int l, int r, int v){
        tree.push_back({-1, -1, 0});
        mom++;

        if(l+1==r){
            return v;
        }

        int m=l+(r-l)/2;
        tree[v].left = build(l, m, mom);
        tree[v].right = build(m, r, mom);

        return v;
    }

    int update(int l, int r, int v, int x){ //returns node index
        if(x<l || r<=x) return v;

        int momold=mom;

        tree.push_back(tree[v]);
        tree[mom].val++;
        mom++;

        if(l+1==r){
            return momold;
        }

        int m=l+(r-l)/2;
        tree[momold].left = update(l, m, tree[v].left, x);
        tree[momold].right = update(m, r, tree[v].right, x);

        return momold;
    }

    int query(int l, int r, int v, int ql, int qr){ //returns sum
        if(qr<=l || r<=ql) return 0;
        if(ql<=l && r<=qr){
            return tree[v].val;
        }
        
        int m=l+(r-l)/2;
        return query(l, m, tree[v].left, ql, qr) + query(m, r, tree[v].right, ql, qr);
    }

};
segtree seg;
int n=0;

void init(int N, int a[], int b[]) {
    n=N;

    seg.build(0, n+1, 0);
    seg.root[-1]=0;

    vector<int> sorted(n, 0);
    iota(sorted.begin(), sorted.end(), 0);
    sort(sorted.begin(), sorted.end(), [&](int i, int j){
        return a[i]<a[j];
    });


    int last=0;
    for(auto i: sorted){


        seg.root[a[i]] = seg.update(0, n+1, last, b[i]);
        last = seg.root[a[i]];
    }

    last=0;
    for(int i=0; i<=n; i++){
        if(seg.root[i]==0){
            seg.root[i] = last;
        }
        else{
            last = seg.root[i];
        }
    }

    n++;
}

int can(int m, int K[]) {

    vector<int> k(m);
    for(int i=0; i<m; i++){
        k[i]=K[i];
    }
    sort(k.begin(), k.end());
    k.push_back(n);

    bool pos=true;
    int add=0;
    for(int i=0; i<m; i++){

        int r=seg.root[k[i]];

        int tot = seg.query(0, n, r, k[i], n);
        if(tot < k[i]+add){
            pos=false;
        }

        int sumuntilnext=seg.query(0, n, r, k[i], k[i+1]);
        add = max(0, k[i]+add - sumuntilnext);
    }

    if(0<add) pos=false;

    return pos;
}

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