oj.uz

Submission #916860

# Submission time Handle Problem Language Result Execution time Memory
916860 2024-01-26T15:37:41 Z pan Curtains (NOI23_curtains) C++17
0 / 100
 742 ms 59956 KB 
#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+1);
		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;
}

Compilation message

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.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Incorrect 1 ms 348 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Incorrect 1 ms 348 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Incorrect 1 ms 348 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 4 ms 604 KB Output is correct
6 Correct 4 ms 844 KB Output is correct
7 Correct 4 ms 604 KB Output is correct
8 Correct 626 ms 47996 KB Output is correct
9 Correct 632 ms 49036 KB Output is correct
10 Correct 742 ms 59956 KB Output is correct
11 Correct 621 ms 48300 KB Output is correct
12 Correct 176 ms 20588 KB Output is correct
13 Correct 178 ms 20168 KB Output is correct
14 Correct 173 ms 20416 KB Output is correct
15 Correct 172 ms 20584 KB Output is correct
16 Correct 167 ms 20356 KB Output is correct
17 Incorrect 178 ms 20172 KB Output isn't correct
18 Halted 0 ms 0 KB -

Subtask #5
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Incorrect 1 ms 348 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Incorrect 1 ms 348 KB Output isn't correct
7 Halted 0 ms 0 KB -