Submission #891719

#	Time	Username	Problem	Language	Result	Execution time	Memory
891719		pubin06	Curtains (NOI23_curtains)	C++14	100 / 100	635 ms	123644 KiB

curtains

#include <bits/stdc++.h>
#define fi first
#define se second
#define sz(v) (int)(v).size()
using namespace std;

const int MXn = 500005;

int n, m, q;
int BIT1[MXn], BIT2[MXn];
void update1(int R, int i, int val) {
	for (; i <= R; i += (i & (-i))) BIT1[i] = min(BIT1[i], val);
}
int get1(int i) {
	int res1 = n + 1;
	for (; i; i -= (i & (-i))) res1 = min(res1, BIT1[i]);
	return res1;
}
void update2(int i, int val) {
	for (; i; i -= (i & (-i))) BIT2[i] = max(BIT2[i], val);
}
int get2(int R, int i) {
	int res2 = 0;
	for (; i <= R; i += (i & (-i))) res2 = max(res2, BIT2[i]);
	return res2;
}

bool onRange(int x, int L, int R) {
	return L <= x && x <= R;
}
int Lf[MXn], Rt[MXn];
bool ans[MXn];
vector<int> r[MXn], l[MXn];
void DnC(int lo, int hi, vector<pair<int, int>> segs, vector<pair<pair<int, int>, int>> qries) {
	if (lo == hi) {
		if (sz(segs)) {
			for (auto qry: qries) {
				ans[qry.se] = true;
			}
		}
		return;
	}
	int mid = (lo + hi) >> 1;
	vector<pair<int, int>> segsL, segsR;
	vector<pair<pair<int, int>, int>> qL, qR;
	for (int i = lo; i <= hi; i++) {
		r[i].clear(), l[i].clear();
	}
	for (auto seg: segs) {
		if (seg.se <= mid) segsL.push_back(seg);
		else r[seg.se].push_back(seg.fi);
		if (seg.fi > mid) segsR.push_back(seg);
		else l[seg.fi].push_back(seg.se);
	}
	for (int i = 1; i <= mid - lo + 1; i++) BIT1[i] = n + 1;
	for (int i = 1; i <= hi - mid; i++) BIT2[i] = 0;
	for (int i = mid; i >= lo; i--) {
		Lf[i] = n + 1;
		for (int j: l[i]) {
			if (j < mid) {
				Lf[i] = min(Lf[i], get1(j + 1 - lo + 1));
			} else {
				Lf[i] = min(Lf[i], j);
			}
		}
		update1(mid - lo + 1, i - lo + 1, Lf[i]);
	}
	for (int j = mid + 1; j <= hi; j++) {
		Rt[j] = 0;
		for (int i: r[j]) {
			if (i > mid + 1) {
				Rt[j] = max(Rt[j], get2(hi - mid, i - 1 - mid));
			} else {
				Rt[j] = max(Rt[j], i);
			}
		}
		update2(j - mid, Rt[j]);
	}
	for (auto qry: qries) {
		int L = qry.fi.fi, R = qry.fi.se;
		if (R <= mid) {
			qL.push_back(qry);
		} else if (L > mid) {
			qR.push_back(qry);
		} else {
			if (onRange(Lf[L], mid, R) && onRange(Rt[R], L, mid + 1)) ans[qry.se] = true;
		}
	}
	
	if (lo <= mid && sz(segsL) && sz(qL)) DnC(lo, mid, segsL, qL);
	if (mid + 1 <= hi && sz(segsR) && sz(qR)) DnC(mid + 1, hi, segsR, qR);
}
vector<pair<int, int>> segs;
vector<pair<pair<int, int>, int>> qries;

signed main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    
    #define TASK "CURTAINS"
    if (ifstream(TASK".INP")) {
    	freopen(TASK".INP", "r", stdin);
    	freopen(TASK".OUT", "w", stdout);
    }
    
    scanf("%d%d%d", &n, &m, &q);
    for (int i = 1, li, ri; i <= m; i++) {
    	scanf("%d%d", &li, &ri);
    	segs.push_back({li, ri});
    }
    for (int i = 1, u, v; i <= q; i++) {
    	scanf("%d%d", &u, &v);
    	qries.push_back({{u, v}, i});
    }
    DnC(1, n, segs, qries);
    for (int i = 1; i <= q; i++) printf(ans[i] ? "YES\n" : "NO\n");
    
    return 0;
}
// Revive! >:)

Compilation message (stderr)

curtains.cpp: In function 'int main()':
curtains.cpp:102:13: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  102 |      freopen(TASK".INP", "r", stdin);
      |      ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
curtains.cpp:103:13: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  103 |      freopen(TASK".OUT", "w", stdout);
      |      ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
curtains.cpp:106:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  106 |     scanf("%d%d%d", &n, &m, &q);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~
curtains.cpp:108:11: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  108 |      scanf("%d%d", &li, &ri);
      |      ~~~~~^~~~~~~~~~~~~~~~~~
curtains.cpp:112:11: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  112 |      scanf("%d%d", &u, &v);
      |      ~~~~~^~~~~~~~~~~~~~~~

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