| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 970702 |
2024-04-27T05:53:45 Z |
hqminhuwu |
Teams (IOI15_teams) |
C++14 |
|
553 ms |
188760 KB |
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair <ll,ll> pll;
typedef pair <int,int> pii;
typedef pair <pii, int> piii;
#define forr(_a,_b,_c) for(int _a = (_b); _a <= (_c); ++_a)
#define ford(_a,_b,_c) for(int _a = (_b) + 1; _a --> (_c);)
#define forf(_a,_b,_c) for(int _a = (_b); _a < (_c); ++_a)
#define st first
#define nd second
#define pb push_back
#define mp make_pair
#define all(x) begin(x),end(x)
#define mask(i) (1LL << (i))
#define bit(x, i) (((x) >> (i)) & 1)
#define bp __builtin_popcountll
#define file "test"
const int N = 5e5 + 5;
const ll oo = 1e9;
const ll mod = 1e9 + 7; // 998244353;
struct node {
pii val;
int l, r;
node () : val({oo, oo}), l(0), r(0){}
};
node tree[20 * N];
int cnt, n;
piii d[N], e[N];
int update (int pre, int l, int r, int pos){
if (l == r){
tree[++cnt].val = {e[l].nd, l};
return cnt;
}
int mid = (l + r) >> 1;
int i = ++cnt;
tree[i] = tree[pre];
if (pos <= mid)
tree[i].l = update(tree[pre].l, l, mid, pos);
else tree[i].r = update(tree[pre].r, mid + 1, r, pos);
tree[i].val = min (tree[tree[i].l].val, tree[tree[i].r].val);
return i;
}
pii get (int i, int l, int r, int u, int v){
if (r < u || l > v) return {oo, oo};
if (l >= u && r <= v)
return tree[i].val;
int mid = (l + r) >> 1;
return min(get(tree[i].l, l, mid, u, v), get(tree[i].r, mid + 1, r, u, v));
}
void mdf (int i, int l, int r, int pos, pii val){
if (l == r){
tree[i].val = val;
return;
}
int mid = (l + r) >> 1;
if (pos <= mid)
mdf(tree[i].l, l, mid, pos, val);
else mdf(tree[i].r, mid + 1, r, pos, val);
tree[i].val = min (tree[tree[i].l].val, tree[tree[i].r].val);
}
vector <int> z, y;
int pos[N], root[N];
void init (int num, int a[], int b[]){
n = num;
forr (i, 1, n){
d[i] = {{a[i - 1], b[i - 1]}, i};
e[i] = {{b[i - 1], a[i - 1]}, i};
z.pb(a[i - 1]);
y.pb(b[i - 1]);
}
sort(d + 1, d + 1 + n);
sort(e + 1, e + 1 + n);
z.pb(0);
y.pb(0);
sort(all(z));
sort(all(y));
forr (i, 1, n){
pos[e[i].nd] = i;
//cout << d[i].st.st << " " << d[i].st.nd << " " << d[i].nd << "\n";
}
// for (int u : z){
// cout << u << " ";
// }
// cout << "\n";
forr (i, 1, n){
root[i] = update(root[i - 1], 1, n, pos[i]);
}
z.pb(oo);
}
int can (int m, int k[]){
sort(k, k + m);
vector <piii> q;
int flag = 1;
forf (i, 0, m){
if (k[i] < z[1] || k[i] > y.back()){
flag = 0;
break;
}
int u = upper_bound(all(z), k[i]) - z.begin() - 1;
int v = lower_bound(all(y), k[i]) - y.begin();
pii tmp = get(root[u], 1, n, v, n);
if (tmp.st > n)
flag = 0;
else {
q.pb({tmp, root[u]});
mdf(root[u], 1, n, tmp.nd, {oo, oo});
}
}
for (piii t : q){
mdf(t.nd, 1, n, t.st.nd, t.st);
}
return flag;
}
Compilation message
teams.cpp: In function 'int can(int, int*)':
teams.cpp:127:49: warning: conversion from '__gnu_cxx::__normal_iterator<int*, std::vector<int> >::difference_type' {aka 'long int'} to 'int' may change value [-Wconversion]
127 | int u = upper_bound(all(z), k[i]) - z.begin() - 1;
| ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~
teams.cpp:128:37: warning: conversion from '__gnu_cxx::__normal_iterator<int*, std::vector<int> >::difference_type' {aka 'long int'} to 'int' may change value [-Wconversion]
128 | int v = lower_bound(all(y), k[i]) - y.begin();
| ~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
72 ms |
158036 KB |
Output is correct |
| 2 |
Incorrect |
46 ms |
158032 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
109 ms |
164292 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
132 ms |
164680 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
553 ms |
188760 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
