| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1083588 | vladilius | Teams (IOI15_teams) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#include "teams.h"
using namespace std;
using ll = long long;
using pii = pair<int, int>;
#define pb push_back
#define ff first
#define ss second
#define ins insert
int n;
vector<int> a, b;
vector<pii> all;
void init(int N, int A[], int B[]){
n = N;
a.resize(n + 1);
for (int i = 1; i <= n; i++) a[i] = A[i - 1];
b.resize(n + 1);
for (int i = 1; i <= n; i++) b[i] = B[i - 1];
all.pb({0, 0});
for (int i = 1; i <= n; i++) all.pb({b[i], a[i]});
sort(all.begin(), all.end());
}
int sum(int x, int x1, int y1, int x2){
int out = 0;
for (int i = 1; i <= x; i++){
out += (x1 <= all[i].ss && all[i].ss <= x2 && all[i].ff >= y1);
}
return out;
}
int sum1(int x1, int y1, int x2, int y2){
int out = 0;
for (int i = 1; i <= n; i++){
out += (x1 <= all[i].ss && all[i].ss <= x2 && y1 <= all[i].ff && all[i].ff <= y2);
}
return out;
}
vector<int> :: iterator it1, it2;
int can(int m, int K[]){
vector<int> k(m + 1);
for (int i = 1; i <= m; i++) k[i] = K[i - 1];
sort(k.begin() + 1, k.end());
vector<pii> st;
vector<int> pr = {0};
auto add = [&](int k, int x){
while (!st.empty() && st.back().ss <= x){
st.pop_back();
pr.pop_back();
}
if (st.empty()) pr.pb(sum(x, 0, 0, k));
else pr.pb(pr.back() + sum(x, st.back().ff + 1, 0, k));
st.pb({k, x});
};
auto get = [&](int k, int x){
if (all[x].ff < k) return 0;
if (st.empty()) return sum(x, 0, k, k);
int l = 0, r = (int) st.size() - 1;
while (l + 1 < r){
int m = (l + r) / 2;
if (st[m].ss < x){
r = m - 1;
}
else {
l = m;
}
}
if (st[r].ss >= x) l = r;
if (st[l].ss < x) l = -1;
int out = sum(x, 0, k, k);
if (l != -1) out -= sum(x, 0, k, st[l].ff);
if (l + 1 < pr.size()) out -= (pr.back() - pr[l + 1] - sum1((l != -1) ? (st[l].ff + 1) : 0, 0, st.back().ff, k - 1));
return out;
};
for (int i = 1; i <= m; i++){
while (!st.empty() && all[st.back().ss].ff < k[i]){
st.pop_back();
pr.pop_back();
}
if (get(k[i], n) < k[i]) return 0;
int l = 1, r = n;
while (l + 1 < r){
int m = (l + r) / 2;
if (get(k[i], m) < k[i]){
l = m + 1;
}
else {
r = m;
}
}
if (get(k[i], l) == k[i]) r = l;
add(k[i], r);
}
return 1;
}
int main(){
int n; cin>>n;
int A[n], B[n];
for (int i = 0; i < n; i++){
cin>>A[i]>>B[i];
}
init(n, A, B);
int q; cin>>q;
while (q--){
int m; cin>>m;
int K[m];
for (int i = 0; i < m; i++){
cin>>K[i];
}
cout<<can(m, K)<<"\n";
}
}