Submission #916866

#	Time	Username	Problem	Language	Result	Execution time	Memory
916866		pan	Curtains (NOI23_curtains)	C++17	100 / 100	1440 ms	152172 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)
{
	vector<pii> leftone, rightone;
	if (queries.empty()) return;
	if (from==to) 
	{
		bool pos = false;
		for (ll u: rightt[from]) if (u==to) {pos=true; break;}
		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--)
	{
		
		ll aftermid = INF;
		toright[i] = INF;
		ll befmid = -INF;
		for (ll u: rightt[i]) 
		{
			if (u>to) continue;
			if (u>=mid) aftermid = min(aftermid, u);
			else befmid = max(befmid, u);
		}
		toright[i] = min(toright[i], aftermid);
		while (que.size() && (que.back().s<=befmid+1 || que.back().f>=toright[i]))
		{
			toright[i] = min(toright[i], que.back().f);
			que.pop_back();
		}
		que.push_back(mp(toright[i], i));
	}
	que.clear();
	for (ll i = mid+1; i<=to; i++)
	{
		ll aftermid = -INF;
		toleft[i] = -INF;
		ll befmid = INF;
		for (ll u: leftt[i]) 
		{
			if (u<from) continue;
			if (u<=mid+1) aftermid = max(aftermid, u);
			else befmid = min(befmid, u);
		}
		toleft[i] = max(toleft[i], aftermid);
		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));
	}
	for (pii u: queries)
	{
		if (u.f.f <mid+1 && 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));
	}
	dnc(1, n, queries);
	for (ll i=0; i<q; ++i) 
	{
		if (ans[i]) cout << "YES" << endl;
		else cout << "NO" << endl;
	}
	
	return 0;
}

Compilation message (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:105:2: note: in expansion of macro 'input'
  105 |  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:105:12: note: in expansion of macro 'input'
  105 |  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:105:22: note: in expansion of macro 'input'
  105 |  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:111:3: note: in expansion of macro 'input'
  111 |   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:111:13: note: in expansion of macro 'input'
  111 |   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:117:3: note: in expansion of macro 'input'
  117 |   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:117:13: note: in expansion of macro 'input'
  117 |   input(l); input(r);
      |             ^~~~~

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