이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 5e5 + 3;
int n, m, q;
pair<int, int> a[N], d[N];
namespace Sub12{
bool valid_input(){ return n <= 2000 and m <= 2000 and q <= 2000; }
void solve(){
for(int i = 1; i <= q; ++i){
vector<int> ck(n + 2, 0);
for(int j = 1; j <= m; ++j){
if(d[i].first <= a[j].first and a[j].second <= d[i].second)
++ck[a[j].first], --ck[a[j].second + 1];
}
for(int j = 1; j <= n; ++j)
ck[j] += ck[j - 1];
bool ok = 1;
for(int j = d[i].first; j <= d[i].second; ++j)
ok &= (ck[j] > 0);
cout << (ok ? "YES\n" : "NO\n");
}
}
}
namespace Sub3{
bool valid_input(){ return n <= 2000; }
bool has[2003][2003], ok[2003][2003];
int p[2003][2003];
void solve(){
for(int i = 1; i <= m; ++i){
has[a[i].first][a[i].second] = 1;
p[a[i].first][a[i].second] = 1;
}
for(int i = 1; i <= n; ++i)
for(int j = 1; j <= i; ++j)
p[j][i] += p[j - 1][i];
for(int i = 1; i <= n; ++i){
int cur = i - 1;
for(int j = i; j <= n; ++j){
if(has[i][j])
ok[i][j] = 1;
else
ok[i][j] = (cur >= i ? p[cur + 1][j] - p[i - 1][j] : 0);
cur = (ok[i][j] ? j : cur);
}
}
for(int i = 1; i <= q; ++i)
cout << (ok[d[i].first][d[i].second] ? "YES\n" : "NO\n");
}
}
namespace Sub4{
bool valid_input(){
bool ok = 1;
for(int i = 1; i <= q; ++i)
ok &= (d[i].first == 1);
return ok;
}
bool has[N], f[N];
vector<int> rv[N];
void solve(){
for(int i = 1; i <= m; ++i){
if(a[i].first == 1)
has[a[i].second] = 1;
rv[a[i].second].push_back(i);
}
int cur = 0;
for(int i = 1; i <= n; ++i){
if(has[i])
f[i] = 1;
else{
for(int x : rv[i])
f[i] |= (a[x].first <= cur);
}
if(f[i])
cur = i + 1;
}
for(int i = 1; i <= q; ++i)
cout << (f[d[i].second] ? "YES\n" : "NO\n");
}
}
signed main(){
cin.tie(nullptr)->sync_with_stdio(false);
cin >> n >> m >> q;
for(int i = 1; i <= m; ++i)
cin >> a[i].first >> a[i].second;
for(int i = 1; i <= q; ++i)
cin >> d[i].first >> d[i].second;
if(Sub12::valid_input())
Sub12::solve();
else if(Sub3::valid_input())
Sub3::solve();
else if(Sub4::valid_input())
Sub4::solve();
}
# | 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... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |