제출 #916852

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
916852		pan	Curtains (NOI23_curtains)	C++17	0 / 100	730 ms	67288 KiB

curtains

#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);
      |             ^~~~~

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