# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
600210 |
2022-07-20T14:25:33 Z |
Bench0310 |
Teams (IOI15_teams) |
C++17 |
|
1207 ms |
128580 KB |
#include <bits/stdc++.h>
#include "teams.h"
using namespace std;
typedef long long ll;
const int N=500000;
int n;
vector<int> tree[4*N];
void update(int idx,int l,int r,int pos,int x)
{
tree[idx].push_back(x);
if(l<r)
{
int m=(l+r)/2;
if(pos<=m) update(2*idx,l,m,pos,x);
else update(2*idx+1,m+1,r,pos,x);
}
}
int query(int idx,int l,int r,int ql,int qr,int lim)
{
if(ql>qr) return 0;
if(l==ql&&r==qr) return (upper_bound(tree[idx].begin(),tree[idx].end(),lim)-tree[idx].begin());
int m=(l+r)/2;
return query(2*idx,l,m,ql,min(qr,m),lim)+query(2*idx+1,m+1,r,max(ql,m+1),qr,lim);
}
void init(int tn,int A[],int B[])
{
n=tn;
vector<array<int,2>> v(n);
for(int i=0;i<n;i++) v[i]={B[i],A[i]};
sort(v.begin(),v.end());
for(auto [b,a]:v) update(1,1,n,a,b);
}
int can(int m,int K[])
{
vector<int> a={0};
for(int i=0;i<m;i++) a.push_back(K[i]);
sort(a.begin(),a.end());
auto f=[&](int l,int r)->int{return query(1,1,n,l,r,r);};
vector<ll> s(m+1,0);
ll mn=0;
bool ok=1;
for(int i=1;i<=m;i++)
{
s[i]=s[i-1]-f(a[i-1]+1,a[i]-1)-a[i];
ll t=-s[i]-a[i]-f(1,a[i]-1);
mn=min(mn,t);
ok&=(n+s[i]-f(a[i]+1,n)+mn>=0);
}
return ok;
}
Compilation message
teams.cpp: In function 'int query(int, int, int, int, int, int)':
teams.cpp:25:80: warning: conversion from '__gnu_cxx::__normal_iterator<int*, std::vector<int> >::difference_type' {aka 'long int'} to 'int' may change value [-Wconversion]
25 | if(l==ql&&r==qr) return (upper_bound(tree[idx].begin(),tree[idx].end(),lim)-tree[idx].begin());
| ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
22 ms |
47188 KB |
Output is correct |
2 |
Correct |
23 ms |
47220 KB |
Output is correct |
3 |
Correct |
24 ms |
47164 KB |
Output is correct |
4 |
Correct |
27 ms |
47188 KB |
Output is correct |
5 |
Correct |
23 ms |
47276 KB |
Output is correct |
6 |
Correct |
24 ms |
47432 KB |
Output is correct |
7 |
Correct |
24 ms |
47268 KB |
Output is correct |
8 |
Correct |
23 ms |
47188 KB |
Output is correct |
9 |
Incorrect |
23 ms |
47260 KB |
Output isn't correct |
10 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
98 ms |
61784 KB |
Output is correct |
2 |
Correct |
101 ms |
61668 KB |
Output is correct |
3 |
Correct |
107 ms |
61772 KB |
Output is correct |
4 |
Correct |
129 ms |
63228 KB |
Output is correct |
5 |
Correct |
45 ms |
57716 KB |
Output is correct |
6 |
Correct |
45 ms |
57840 KB |
Output is correct |
7 |
Incorrect |
45 ms |
57716 KB |
Output isn't correct |
8 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
142 ms |
62024 KB |
Output is correct |
2 |
Correct |
177 ms |
61968 KB |
Output is correct |
3 |
Correct |
326 ms |
65140 KB |
Output is correct |
4 |
Correct |
137 ms |
63188 KB |
Output is correct |
5 |
Correct |
96 ms |
57932 KB |
Output is correct |
6 |
Correct |
109 ms |
58016 KB |
Output is correct |
7 |
Incorrect |
87 ms |
57976 KB |
Output isn't correct |
8 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
805 ms |
124284 KB |
Output is correct |
2 |
Correct |
802 ms |
124292 KB |
Output is correct |
3 |
Correct |
1207 ms |
128580 KB |
Output is correct |
4 |
Correct |
723 ms |
124712 KB |
Output is correct |
5 |
Correct |
246 ms |
103276 KB |
Output is correct |
6 |
Correct |
253 ms |
103268 KB |
Output is correct |
7 |
Incorrect |
248 ms |
103220 KB |
Output isn't correct |
8 |
Halted |
0 ms |
0 KB |
- |