제출 #916852

#제출 시각아이디문제언어결과실행 시간메모리
916852panCurtains (NOI23_curtains)C++17
0 / 100
730 ms67288 KiB
#include <bits/stdc++.h> //#include "bits_stdc++.h" #include <stdio.h> #include <algorithm> #include <memory.h> #define f first #define s second #define mp make_pair #define pb push_back #define lb lower_bound #define ub upper_bound #define input(x) scanf("%lld", &x); #define print(x, y) printf("%lld%c", x, y); #define show(x) cerr << #x << " is " << x << endl; #define show2(x,y) cerr << #x << " is " << x << " " << #y << " is " << y << endl; #define show3(x,y,z) cerr << #x << " is " << x << " " << #y << " is " << y << " " << #z << " is " << z << endl; using namespace std; typedef long long ll; typedef long double ld; typedef pair<ld, ll> pd; typedef pair<string, ll> psl; typedef pair<ll, ll> pi; typedef pair<pi, ll> pii; ll n, m, q, l ,r; ll const INF = 1e13; vector<vector<ll> > leftt, rightt; vector<pii> queries; vector<bool> ans; vector<ll> toright, toleft; void dnc(ll from, ll to, vector<pii> queries) { //show2(from, to); vector<pii> leftone, rightone; if (queries.empty()) return; if (from==to) { bool pos = lb(leftt[from].begin(), leftt[from].end(), to)!=leftt[from].end() && (*lb(leftt[from].begin(), leftt[from].end(), to))==to; for (pii u: queries) ans[u.s] = pos; return; } ll mid = (from+to)/2; toright.clear(); toleft.clear(); deque<pi> que;// (val, i) for (ll i = mid; i>=from; i--) { auto it = lb(rightt[i].begin(), rightt[i].end(), mid); ll aftermid = INF; if (it!=rightt[i].end()) aftermid = *it; toright[i] = INF; if (aftermid<=to) toright[i] = min(toright[i], aftermid); ll befmid = -INF; if (it!=rightt[i].begin()) befmid = *(--it); while (que.size() && (que.back().s<=befmid+1 || que.back().f>=toright[i])) { toright[i] = min(toright[i], que.back().f); que.pop_back(); } //show2(i, toright[i]); que.push_back(mp(toright[i], i)); //show3(i, aftermid, befmid); } que.clear(); for (ll i = mid+1; i<=to; i++) { auto it = ub(leftt[i].begin(), leftt[i].end(), mid); auto newit = it; ll aftermid = -INF; toleft[i] = -INF; if (it!=leftt[i].begin()) aftermid = *(--it); if (aftermid>=from) toleft[i] = max(toleft[i], aftermid); ll befmid = INF; if (newit!=leftt[i].end()) befmid = *(newit); while (que.size() && (que.back().s>=befmid-1 || que.back().f<=toleft[i])) { toleft[i] = max(toleft[i], que.back().f); que.pop_back(); } que.push_back(mp(toleft[i], i)); //show2(i, toleft[i]); //show3(i, aftermid, befmid); } for (pii u: queries) { if (u.f.f <mid && u.f.s>mid) { ans[u.s] = (toright[u.f.f]<=u.f.s && toleft[u.f.s]>=u.f.f); } else if (u.f.s <= mid) { leftone.pb(u); } else { rightone.pb(u); } } dnc(from, mid, leftone); dnc(mid+1, to, rightone); } int main() { input(n); input(m); input(q); leftt.resize(n+1); rightt.resize(n+1); toleft.resize(n+1); toright.resize(n+1); ans.resize(q); for (ll i=0; i<m; ++i) { input(l); input(r); leftt[r].pb(l); rightt[l].pb(r); } for (ll i=0; i<q; ++i) { input(l); input(r); queries.pb(mp(mp(l, r), i)); } for (ll i=1; i<=n; ++i) sort(leftt[i].begin(), leftt[i].end()); for (ll i=1; i<=n; ++i) sort(rightt[i].begin(), rightt[i].end()); dnc(1, n, queries); for (ll i=0; i<q; ++i) { if (ans[i]) cout << "YES" << endl; else cout << "NO" << endl; } return 0; }

컴파일 시 표준 에러 (stderr) 메시지

curtains.cpp: In function 'int main()':
curtains.cpp:12:23: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   12 | #define input(x) scanf("%lld", &x);
      |                  ~~~~~^~~~~~~~~~~~
curtains.cpp:103:2: note: in expansion of macro 'input'
  103 |  input(n); input(m); input(q);
      |  ^~~~~
curtains.cpp:12:23: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   12 | #define input(x) scanf("%lld", &x);
      |                  ~~~~~^~~~~~~~~~~~
curtains.cpp:103:12: note: in expansion of macro 'input'
  103 |  input(n); input(m); input(q);
      |            ^~~~~
curtains.cpp:12:23: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   12 | #define input(x) scanf("%lld", &x);
      |                  ~~~~~^~~~~~~~~~~~
curtains.cpp:103:22: note: in expansion of macro 'input'
  103 |  input(n); input(m); input(q);
      |                      ^~~~~
curtains.cpp:12:23: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   12 | #define input(x) scanf("%lld", &x);
      |                  ~~~~~^~~~~~~~~~~~
curtains.cpp:109:3: note: in expansion of macro 'input'
  109 |   input(l); input(r);
      |   ^~~~~
curtains.cpp:12:23: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   12 | #define input(x) scanf("%lld", &x);
      |                  ~~~~~^~~~~~~~~~~~
curtains.cpp:109:13: note: in expansion of macro 'input'
  109 |   input(l); input(r);
      |             ^~~~~
curtains.cpp:12:23: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   12 | #define input(x) scanf("%lld", &x);
      |                  ~~~~~^~~~~~~~~~~~
curtains.cpp:115:3: note: in expansion of macro 'input'
  115 |   input(l); input(r);
      |   ^~~~~
curtains.cpp:12:23: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   12 | #define input(x) scanf("%lld", &x);
      |                  ~~~~~^~~~~~~~~~~~
curtains.cpp:115:13: note: in expansion of macro 'input'
  115 |   input(l); input(r);
      |             ^~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...