Submission #1162049

#	Time	Username	Problem	Language	Result	Execution time	Memory
1162049		veehj	Curtains (NOI23_curtains)	C++20	0 / 100	1 ms	532 KiB

curtains

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define fi first
#define se second
#define pb push_back
#define sz(a) (ll) a.size()
#define all(x) (x).begin(), (x).end()
ll n, m, q;
vector<ll> l, r, s, e;

void f() {
  cin >> n >> m >> q;
  l.resize(m);
  r.resize(m);
  s.resize(q);
  e.resize(q);
  vector<vector<bool>> dp(n+3, vector<bool>(n+3, 0));
  vector<set<ll>> frnt(n+3, (set<ll>){});
  vector<ll> mn(n+3, n+3);
  for(ll i=0; i<m; i++){ 
    cin >> l[i] >> r[i]; 
    l[i]--; r[i]--;
    mn[l[i]]=min(mn[l[i]], r[i]); 
    frnt[r[i]].insert(l[i]);
  }
  for(ll i=0; i<q; i++){ cin >> s[i] >> e[i]; s[i]--; e[i]--; }
  for(ll i=0; i<n; i++){
    if(mn[i]>=n) continue;
    ll lst=mn[i];
    dp[i][lst]=1;
    for(ll j=lst+1; j<n; j++){
      if(frnt[j].empty()) continue;
      auto poin=lower_bound(all(frnt[j]), lst);
      if(poin!=frnt[j].end() && lst>=(*poin)-1){
        lst=j;
        dp[i][j]=1;
      }
    }
  }
  for(ll i=0; i<q; i++){
    if(dp[s[i]][e[i]]) cout << "YES";
    else cout << "NO";
    if(i!=q-1) cout << endl;
  }
}

int main() {
  int tc=1; 
  // cin >> tc;
  for(int i=1; i<=tc; i++){
    // cout << '#' << i << endl;
    f();
    if(i!=tc) cout << endl;
  }
}

• Subtask 1: 0 / 3
• Subtask 2: 0 / 6
• Subtask 3: 0 / 15
• Subtask 4: 0 / 20
• Subtask 5: 0 / 36
• Subtask 6: 0 / 20