Submission #143058

#	Time	Username	Problem	Language	Result	Execution time	Memory
143058		neki	Teams (IOI15_teams)	C++14	0 / 100	321 ms	32120 KiB

teams

#include <bits/stdc++.h>
#define loop(i, a, b) for(long long i=a;i<b;i++)
#define maxn 200100
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;

int n, *a, *b, c[maxn];
pii arr[maxn];
vector<int> tree[2*maxn];

int ch(int ta, int tb){
    int ans=0, l=lower_bound(a, a+n, ta)-a, r=n;
    for(l+=n, r+=n;l<r;l>>=1, r>>=1){
        if(l&1) {ans+=lower_bound(tree[l].begin(), tree[l].end(), tb)-tree[l].begin(), l++;}
        if(r&1) --r,ans+=upper_bound(tree[r].begin(), tree[r].end(), tb)-tree[r].begin();
    }
    return ans;
}
void init(int N, int A[], int B[]) {
    n=N;a=A;b=B;
    loop(i, 0, n) arr[i].first=a[i],arr[i].second=b[i];
    sort(arr, arr+n);
    sort(a, a+n);sort(b, b+n);
    loop(i, 0, n) for(int j=i+n;j>0;j>>=1) tree[j].push_back(arr[i].second);
    loop(i, 0, 2*n) sort(tree[i].begin(), tree[i].end());
}

int can(int m, int k[]){
    c[m+1];loop(i, 0, m) c[i]=k[i];c[m]=0;
    m++;sort(c, c+m);
    int ints=0;
    loop(i, 1, m){
        int st=lower_bound(a, a+n,c[i])-upper_bound(a, a+n,c[i-1])+1;
        int en=upper_bound(b, b+n,c[i])-lower_bound(b, b+n,c[i-1])+1;
        int temp=ch(c[i-1]+1, c[i]);
        st-=temp;en-=temp;
        ints=max(ints-en, 0);ints+=st-c[i];
        if(ints<0) return 0;
    }
    return 1;
}

Compilation message (stderr)

teams.cpp: In function 'int ch(int, int)':
teams.cpp:13:41: warning: conversion to 'int' from 'long int' may alter its value [-Wconversion]
     int ans=0, l=lower_bound(a, a+n, ta)-a, r=n;
                  ~~~~~~~~~~~~~~~~~~~~~~~^~
teams.cpp:15:85: warning: conversion to 'int' from '__gnu_cxx::__normal_iterator<int*, std::vector<int> >::difference_type {aka long int}' may alter its value [-Wconversion]
         if(l&1) {ans+=lower_bound(tree[l].begin(), tree[l].end(), tb)-tree[l].begin(), l++;}
                                                                                     ^
teams.cpp:16:88: warning: conversion to 'int' from '__gnu_cxx::__normal_iterator<int*, std::vector<int> >::difference_type {aka long int}' may alter its value [-Wconversion]
         if(r&1) --r,ans+=upper_bound(tree[r].begin(), tree[r].end(), tb)-tree[r].begin();
                                                                                        ^
teams.cpp: In function 'void init(int, int*, int*)':
teams.cpp:25:30: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
     loop(i, 0, n) for(int j=i+n;j>0;j>>=1) tree[j].push_back(arr[i].second);
                             ~^~
teams.cpp: In function 'int can(int, int*)':
teams.cpp:30:10: warning: statement has no effect [-Wunused-value]
     c[m+1];loop(i, 0, m) c[i]=k[i];c[m]=0;
     ~~~~~^
teams.cpp:34:67: warning: conversion to 'int' from 'long int' may alter its value [-Wconversion]
         int st=lower_bound(a, a+n,c[i])-upper_bound(a, a+n,c[i-1])+1;
                ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~
teams.cpp:35:67: warning: conversion to 'int' from 'long int' may alter its value [-Wconversion]
         int en=upper_bound(b, b+n,c[i])-lower_bound(b, b+n,c[i-1])+1;
                ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~

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