oj.uz

Submission #916852

# Submission time Handle Problem Language Result Execution time Memory
916852 2024-01-26T15:27:10 Z pan Curtains (NOI23_curtains) C++17
0 / 100
 730 ms 67288 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);
		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 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 344 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 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 344 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 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 344 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 436 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 704 KB Output is correct
6 Correct 4 ms 860 KB Output is correct
7 Correct 4 ms 860 KB Output is correct
8 Correct 634 ms 51260 KB Output is correct
9 Correct 649 ms 52904 KB Output is correct
10 Correct 730 ms 67288 KB Output is correct
11 Correct 641 ms 51124 KB Output is correct
12 Correct 178 ms 21956 KB Output is correct
13 Correct 173 ms 22072 KB Output is correct
14 Correct 172 ms 22208 KB Output is correct
15 Correct 167 ms 22564 KB Output is correct
16 Correct 170 ms 22124 KB Output is correct
17 Incorrect 171 ms 21952 KB Output isn't correct
18 Halted 0 ms 0 KB -

Subtask #5
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 344 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 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 344 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 -