Submission #43483

#	Time	Username	Problem	Language	Result	Execution time	Memory
43483		nonocut	Teams (IOI15_teams)	C++14	0 / 100	3150 ms	62048 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 = 5e5 + 5;

int n;
pii p[maxn];

vector<int> tree[maxn];
vector<int>::iterator used[maxn];
int pos[maxn];

void add(int x, int y) {
    while(x<=n) {
        tree[x].push_back(y);
        x += x&-x;
    }
}

int query(int x, int y) {
    int res = 0;
    while(x>0) {
        if(!tree[x].empty()) {
            auto it = --upper_bound(all(tree[x]), y);
            res += it - used[x];
        }
        x -= x&-x;
    }
    return res;
}

void change(int x, int y) {
    while(x>0) {
        if(!tree[x].empty()) used[x] = --upper_bound(all(tree[x]), y);
        x -= x&-x;
    }
}

void reset(int x) {
    while(x>0) {
        used[x] = --tree[x].begin();
        x -= x&-x;
    }
}

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

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++) 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++) {
        used[i] = --tree[i].begin();
        sort(all(tree[i]));
    }
}

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

Compilation message (stderr)

teams.cpp: In function 'int query(int, int)':
teams.cpp:31:17: warning: conversion to 'int' from '__gnu_cxx::__normal_iterator<int*, std::vector<int> >::difference_type {aka long int}' may alter its value [-Wconversion]
             res += it - used[x];
                 ^

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