이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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);
int flag = 1, low = 0;
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();
v = max (low, v);
pii tmp = get(root[u], 1, n, v, n);
// cout << tmp.st << " " << tmp.nd << " " << low << "\n";
low = max (low, tmp.nd + 1);
if (tmp.st > n){
return 0;
}
}
return flag;
}
컴파일 시 표준 에러 (stderr) 메시지
teams.cpp: In function 'int can(int, int*)':
teams.cpp:126:49: warning: conversion from '__gnu_cxx::__normal_iterator<int*, std::vector<int> >::difference_type' {aka 'long int'} to 'int' may change value [-Wconversion]
126 | int u = upper_bound(all(z), k[i]) - z.begin() - 1;
| ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~
teams.cpp:127:37: warning: conversion from '__gnu_cxx::__normal_iterator<int*, std::vector<int> >::difference_type' {aka 'long int'} to 'int' may change value [-Wconversion]
127 | int v = lower_bound(all(y), k[i]) - y.begin();
| ~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |