Submission #43485

#	Time	Username	Problem	Language	Result	Execution time	Memory
43485		nonocut	Teams (IOI15_teams)	C++14	0 / 100	1175 ms	16080 KiB

teams

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

#define pii pair<int,int>
#define X first
#define Y second
#define all(x) x.begin(), x.end()

const int maxn = 1e5 + 5;

int n;
pii p[maxn];
int rec[maxn];

vector<int> tree[maxn];
int used[maxn];

int sz[maxn];

int bsearch(int x, int val) {
    int l = used[x], r = sz[x]-1, mid, pos = used[x];
    while(l<=r) {
        mid = (l+r)/2;
        if(tree[x][mid]<=val) {
            pos = mid;
            l = mid+1;
        }
        else r = mid-1;
    }
    return pos;
}

void add(int x, int y) {
    while(x<=n) {
//        printf("\t\tadd %d : %d\n",x,y);
        tree[x].push_back(y);
        x += x&-x;
    }
}

int query(int x, int y) {
    int res = 0;
    while(x>0) {
//        printf("\t\tquery %d : %d\n",x,y);
        if(!tree[x].empty()) {
//            printf("\t\t\t");
//            for(auto t : tree[x]) {
//                if(t==used[x]) printf("*");
//                printf("%d ",t);
//            }
//            printf("\n");
            auto it = bsearch(x, y);
            res += it - used[x];
        }
        x -= x&-x;
    }
    return res;
}

void change(int x, int y) {
    while(x>0) {
        if(!tree[x].empty()) {
            if(used[x] < y) {
                used[x] = bsearch(x, y);
//                printf("used %d : %d (%d)\n",x,used[x],y);
            }
        }
        x -= x&-x;
    }
}

void reset(int x) {
    while(x>0) {
        if(!tree[x].empty()) {
            used[x] = 0;
//            printf("used %d : %d\n",x,used[x]);
        }
        x -= x&-x;
    }
}

bool cmp(pii x, pii y) {
    return x.Y < y.Y;
}

int bsearch2(int x) {
    int l,r,mid,pos1,pos2;
    l = 1; r = n; pos1 = 0;
    while(l<=r) {
        mid = (l+r)/2;
        if(rec[mid]<x) {
            pos1 = mid;
            l = mid+1;
        }
        else r = mid-1;
    }
    l = 1; r = n; pos2 = 0;
    while(l<=r) {
        mid = (l+r)/2;
        if(rec[mid]>=rec[pos1]) {
            pos1 = mid;
            r = mid-1;
        }
        else l = mid+1;
    }
//    printf("bsearch2 %d = %d\n",x,pos);
    return pos2;
}

void init(int N, int A[], int B[]) {
    n = N;
    for(int i=0;i<n;i++) p[i] = {A[i],B[i]};
    sort(p,p+n,cmp);
    for(int i=0;i<n;i++) rec[i+1] = p[i].Y, p[i].Y = i+1;
    for(int i=0;i<n;i++) add(p[i].X,p[i].Y);
    for(int i=1;i<=n;i++) {
        tree[i].push_back(0);
        sort(all(tree[i]));
        used[i] = 0;
        sz[i] = tree[i].size();
    }
}

int can(int m, int K[]) {
    int res = 1;
    sort(K, K+m);
    for(int i=0;i<m;i++) reset(K[i]);
    for(int i=0;i<m;i++) {
        change(K[i], bsearch2(K[i]));
//        printf("i = %d\n",i);
        int l = 1, r = n, mid, pos = -1;
        while(l<=r) {
            mid = (l+r)/2;
//            printf("---- bsearch : %d\n",mid);
            if(query(K[i],mid) >= K[i]) {
                pos = mid;
                r = mid-1;
            }
            else l = mid+1;
        }
        if(pos==-1) res = 0;
        change(K[i], pos);
//        printf("------------------------------\n");
    }
    return res;
}

Compilation message (stderr)

teams.cpp: In function 'void init(int, int*, int*)':
teams.cpp:121:15: warning: conversion to 'int' from 'std::vector<int>::size_type {aka long unsigned int}' may alter its value [-Wconversion]
         sz[i] = tree[i].size();
               ^

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