Submission #43520

#	Time	Username	Problem	Language	Result	Execution time	Memory
43520		nonocut	Teams (IOI15_teams)	C++14	0 / 100	200 ms	71192 KiB

teams

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

#define pii pair<int,int>
#define X first
#define Y second

const int maxn = 1e5 + 5;

int n,m;
vector<int> have[maxn];
pii q[maxn];

//persistent tree
struct node {
    int val;
    node *l, *r;
};

node* root[maxn];

node* getnode() {
    node* temp = new node;
    temp->val = 0; temp->l = temp->r = nullptr;
    return temp;
}

void build(node *pos, int l, int r) {
    if(l==r) return ;
    int mid = (l+r)/2;
    pos->l = getnode(); pos->r = getnode();
    build(pos->l, l, mid); build(pos->r, mid+1, r);
    pos->val = pos->l->val + pos->r->val;
}

void upgrade(node *last, node *pos, int l, int r, int x) {
    if(l==r) {
        pos->val = last->val + 1;
        return ;
    }
    int mid = (l+r)/2;
    if(x<=mid) {
        pos->l = getnode();
        pos->r = last->r;
        upgrade(last->l, pos->l, l, mid, x);
    }
    else {
        pos->l = last->l;
        pos->r = getnode();
        upgrade(last->r, pos->r, mid+1, r, x);
    }
    pos->val = pos->l->val + pos->r->val;
}

int query(node *pos, int l, int r, int x, int y) {
    if(r<x || y<l) return 0;
    if(x<=l && r<=y) return pos->val;
    int mid = (l+r)/2;
    return query(pos->l,l,mid,x,y) + query(pos->r,mid+1,r,x,y);
}

void init(int N, int A[], int B[]) {
    n = N;
    for(int i=0;i<n;i++) have[A[i]].push_back(B[i]);
    root[0] = getnode();
    build(root[0],1,n);
    for(int i=1;i<=n;i++) {
        root[i] = root[i-1];
        for(auto x : have[i]) {
            node *temp = getnode();
            upgrade(root[i],temp,1,n,x);
            root[i] = temp;
        }
    }
}

int can(int M, int K[]) {
    sort(K, K+M); m = 0;
    for(int i=0;i<M;i++) {
        if(i==0 || K[i]!=K[i-1]) q[m++] = {K[i], 0};
        q[m].Y += K[i];
    }
}

Compilation message (stderr)

teams.cpp: In function 'int can(int, int*)':
teams.cpp:84:1: warning: no return statement in function returning non-void [-Wreturn-type]
 }
 ^

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