Submission #143043

#	Time	Username	Problem	Language	Result	Execution time	Memory
143043		neki	Teams (IOI15_teams)	C++14	0 / 100	215 ms	37240 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;
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();
        if(r&1) ans+=lower_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[]){
    int 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+1){
        int st=lower_bound(a, a+n,c[i])-upper_bound(a, a+n,c[i-1]);
        int en=upper_bound(b, b+n,c[i])-lower_bound(b, b+n,c[i-1]);
        int temp=ch(c[i-1]+1, c[i]-1);
        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:86: 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();
                                                                                      ^
teams.cpp:15:76: warning: operation on 'l' may be undefined [-Wsequence-point]
         if(l&1) ans+=lower_bound(tree[l].begin(), tree[l].end(), tb)-tree[l++].begin();
                                                                           ~^~
teams.cpp:16:86: 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) ans+=lower_bound(tree[--r].begin(), tree[r].end(), tb)-tree[r].begin();
                                                                                      ^
teams.cpp:16:39: warning: operation on 'r' may be undefined [-Wsequence-point]
         if(r&1) ans+=lower_bound(tree[--r].begin(), tree[r].end(), tb)-tree[r].begin();
                                       ^~~
teams.cpp: In function 'void init(int, int*, int*)':
teams.cpp:2:23: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
 #define loop(i, a, b) for(long long i=a;i<b;i++)
                       ^
teams.cpp:23:5: note: in expansion of macro 'loop'
     loop(i, 0, n) arr[i].first=a[i],arr[i].second=b[i];sort(arr, arr+n);
     ^~~~
teams.cpp:23:56: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
     loop(i, 0, n) arr[i].first=a[i],arr[i].second=b[i];sort(arr, arr+n);
                                                        ^~~~
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:34:40: 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]);
                ~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
teams.cpp:35:40: 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]);
                ~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

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