oj.uz

Submission #1029236

# Submission time Handle Problem Language Result Execution time Memory
1029236 2024-07-20T14:09:03 Z ihne Curtains (NOI23_curtains) C++17
9 / 100
 1500 ms 63160 KB 
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pii pair<int,int>
#define pb push_back
const int mn=5e5+5;
const int mod=1e9+7;
struct query{
  int l,r,id;
};
int a[mn],ans[mn],f[mn];
vector<int> L[mn],R[mn];
void solve(int l,int r,vector<query> q){
  if (l==r){
    int bl=0;
    for (int j:L[l]) if (j==r) bl=1;
    for (int i=0;i<q.size();i++){
      ans[q[i].id]=bl;
    }
    return;
  }
  int mid=l+r>>1;
  stack<int> v;
  for (int i=mid;i>=1;i--){
    f[i]=1e9;
    for (int j:L[i]){
      if (j>=mid) f[i]=min(f[i],j);
      while (!v.empty()&&v.top()-1<=j&&j<=f[v.top()]){
        f[i]=min(f[i],f[v.top()]);
        v.pop();
      }
    }
    v.push(i);
  }
  while (!v.empty()) v.pop();
  for (int i=mid+1;i<=r;i++){
    f[i]=0;
    for (int j:R[i]){
      if (j<=mid+1) f[i]=max(f[i],j);
      while (!v.empty()&&v.top()+1>=j&&j>=f[v.top()]){
        f[i]=max(f[i],f[v.top()]);
        v.pop();
      }
    }
    v.push(i);
  }
  vector<query> vl,vr;
  for (int i=0;i<q.size();i++){
    if (q[i].r<=mid) vl.pb(q[i]);
    else if (q[i].l>mid) vr.pb(q[i]);
    else{
      if (f[q[i].l]<=q[i].r&&f[q[i].r]>=q[i].l) ans[q[i].id]=1;
    }
  }
  solve(l,mid,vl);
  solve(mid+1,r,vr);
}
signed main(){
  //freopen("","r",stdin);
  //freopen("","w",stdout);
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  int n,m,Q;
  cin>>n>>m>>Q;
  for (int i=1;i<=m;i++){
    int l,r;
    cin>>l>>r;
    L[l].pb(r);
    R[r].pb(l);
  }
  vector<query> q;
  for (int i=1;i<=Q;i++){
    int l,r;
    cin>>l>>r;
    q.pb({l,r,i});
  }
  solve(1,n,q);
  for (int i=1;i<=Q;i++){
    if (ans[i]) cout<<"YES\n";
    else cout<<"NO\n";
  }
}

Compilation message

curtains.cpp: In function 'void solve(int, int, std::vector<query>)':
curtains.cpp:18:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<query>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   18 |     for (int i=0;i<q.size();i++){
      |                  ~^~~~~~~~~
curtains.cpp:23:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   23 |   int mid=l+r>>1;
      |           ~^~
curtains.cpp:49:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<query>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |   for (int i=0;i<q.size();i++){
      |                ~^~~~~~~~~

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 23900 KB Output is correct
2 Correct 10 ms 23948 KB Output is correct
3 Correct 10 ms 23900 KB Output is correct
4 Correct 10 ms 23796 KB Output is correct
5 Correct 10 ms 23900 KB Output is correct
6 Correct 9 ms 23900 KB Output is correct
7 Correct 10 ms 23772 KB Output is correct
8 Correct 10 ms 23900 KB Output is correct
9 Correct 9 ms 23780 KB Output is correct
10 Correct 8 ms 23900 KB Output is correct
11 Correct 10 ms 23900 KB Output is correct
12 Correct 9 ms 23808 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 23900 KB Output is correct
2 Correct 10 ms 23948 KB Output is correct
3 Correct 10 ms 23900 KB Output is correct
4 Correct 10 ms 23796 KB Output is correct
5 Correct 10 ms 23900 KB Output is correct
6 Correct 9 ms 23900 KB Output is correct
7 Correct 10 ms 23772 KB Output is correct
8 Correct 10 ms 23900 KB Output is correct
9 Correct 9 ms 23780 KB Output is correct
10 Correct 8 ms 23900 KB Output is correct
11 Correct 10 ms 23900 KB Output is correct
12 Correct 9 ms 23808 KB Output is correct
13 Correct 30 ms 24164 KB Output is correct
14 Correct 22 ms 23964 KB Output is correct
15 Correct 24 ms 24156 KB Output is correct
16 Correct 22 ms 24152 KB Output is correct
17 Correct 23 ms 24156 KB Output is correct
18 Correct 21 ms 24060 KB Output is correct
19 Correct 21 ms 24176 KB Output is correct
20 Correct 17 ms 24260 KB Output is correct
21 Correct 17 ms 24156 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 23900 KB Output is correct
2 Correct 10 ms 23948 KB Output is correct
3 Correct 10 ms 23900 KB Output is correct
4 Correct 10 ms 23796 KB Output is correct
5 Correct 10 ms 23900 KB Output is correct
6 Correct 9 ms 23900 KB Output is correct
7 Correct 10 ms 23772 KB Output is correct
8 Correct 10 ms 23900 KB Output is correct
9 Correct 9 ms 23780 KB Output is correct
10 Correct 8 ms 23900 KB Output is correct
11 Correct 10 ms 23900 KB Output is correct
12 Correct 9 ms 23808 KB Output is correct
13 Correct 30 ms 24164 KB Output is correct
14 Correct 22 ms 23964 KB Output is correct
15 Correct 24 ms 24156 KB Output is correct
16 Correct 22 ms 24152 KB Output is correct
17 Correct 23 ms 24156 KB Output is correct
18 Correct 21 ms 24060 KB Output is correct
19 Correct 21 ms 24176 KB Output is correct
20 Correct 17 ms 24260 KB Output is correct
21 Correct 17 ms 24156 KB Output is correct
22 Correct 104 ms 46168 KB Output is correct
23 Correct 126 ms 48052 KB Output is correct
24 Correct 472 ms 50224 KB Output is correct
25 Execution timed out 1565 ms 58708 KB Time limit exceeded
26 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 23900 KB Output is correct
2 Correct 10 ms 23900 KB Output is correct
3 Correct 15 ms 23900 KB Output is correct
4 Correct 13 ms 23900 KB Output is correct
5 Correct 24 ms 24156 KB Output is correct
6 Correct 23 ms 24168 KB Output is correct
7 Correct 23 ms 24156 KB Output is correct
8 Correct 96 ms 51380 KB Output is correct
9 Correct 308 ms 53680 KB Output is correct
10 Execution timed out 1580 ms 63160 KB Time limit exceeded
11 Halted 0 ms 0 KB -

Subtask #5
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 23900 KB Output is correct
2 Correct 10 ms 23948 KB Output is correct
3 Correct 10 ms 23900 KB Output is correct
4 Correct 10 ms 23796 KB Output is correct
5 Correct 10 ms 23900 KB Output is correct
6 Correct 9 ms 23900 KB Output is correct
7 Correct 10 ms 23772 KB Output is correct
8 Correct 10 ms 23900 KB Output is correct
9 Correct 9 ms 23780 KB Output is correct
10 Correct 8 ms 23900 KB Output is correct
11 Correct 10 ms 23900 KB Output is correct
12 Correct 9 ms 23808 KB Output is correct
13 Correct 30 ms 24164 KB Output is correct
14 Correct 22 ms 23964 KB Output is correct
15 Correct 24 ms 24156 KB Output is correct
16 Correct 22 ms 24152 KB Output is correct
17 Correct 23 ms 24156 KB Output is correct
18 Correct 21 ms 24060 KB Output is correct
19 Correct 21 ms 24176 KB Output is correct
20 Correct 17 ms 24260 KB Output is correct
21 Correct 17 ms 24156 KB Output is correct
22 Execution timed out 1507 ms 31072 KB Time limit exceeded
23 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 23900 KB Output is correct
2 Correct 10 ms 23948 KB Output is correct
3 Correct 10 ms 23900 KB Output is correct
4 Correct 10 ms 23796 KB Output is correct
5 Correct 10 ms 23900 KB Output is correct
6 Correct 9 ms 23900 KB Output is correct
7 Correct 10 ms 23772 KB Output is correct
8 Correct 10 ms 23900 KB Output is correct
9 Correct 9 ms 23780 KB Output is correct
10 Correct 8 ms 23900 KB Output is correct
11 Correct 10 ms 23900 KB Output is correct
12 Correct 9 ms 23808 KB Output is correct
13 Correct 30 ms 24164 KB Output is correct
14 Correct 22 ms 23964 KB Output is correct
15 Correct 24 ms 24156 KB Output is correct
16 Correct 22 ms 24152 KB Output is correct
17 Correct 23 ms 24156 KB Output is correct
18 Correct 21 ms 24060 KB Output is correct
19 Correct 21 ms 24176 KB Output is correct
20 Correct 17 ms 24260 KB Output is correct
21 Correct 17 ms 24156 KB Output is correct
22 Correct 104 ms 46168 KB Output is correct
23 Correct 126 ms 48052 KB Output is correct
24 Correct 472 ms 50224 KB Output is correct
25 Execution timed out 1565 ms 58708 KB Time limit exceeded
26 Halted 0 ms 0 KB -