제출 #1341332

#제출 시각아이디문제언어결과실행 시간메모리
1341332top1svtinGift Exchange (JOI24_ho_t4)C++17
100 / 100
1235 ms90920 KiB
#include <bits/stdc++.h>

using namespace std;

#define kien long long
//#define int long long
#define pb push_back
#define FOR(i, a, b) for (int i = a;i <= b; i++)
#define FORD(i, a, b) for (int i = a;i >= b; i--)
#define pii pair<int, int>
#define dembit(a) __builtin_popcountll(a)
#define task "kien"
#define fin(x) freopen(x".inp","r",stdin)
#define fou(x) freopen(x".out","w",stdout)
#define debug(x) cout << x << " "
#define down cout << "\n"
const kien MOD = 1e9 + 7;
const int NTEST = 100;
const int Million = 1e6;
const int MXN = 5e5 + 5;
const int INF = 1e9;

mt19937 rd(chrono::high_resolution_clock::now().time_since_epoch().count());
kien rand(kien l, kien r) {
	assert(l <= r);
	return uniform_int_distribution<kien>(l, r)(rd);
}

int n, k, m, u, v, h;
int st[4 * MXN], maxx, minn, vtr, s, t, r[MXN], x, l[MXN], timer, ans[MXN], add;
pii a[MXN];
vector <pii> qr[MXN];
vector <int> vec[MXN];

struct segment {
	int st[8 * MXN];
	int lazy[8 * MXN];
	void pushx (int id) {
		st[id << 1] = max(lazy[id], st[id << 1]);
		st[id << 1 | 1] = max(st[id << 1 | 1], lazy[id]);

		lazy[id << 1] = max(lazy[id << 1], lazy[id]);
		lazy[id << 1 | 1] = max(lazy[id << 1 | 1], lazy[id]);

		lazy[id] = 0;
	}

	void updatex (int id, int l, int r, int u, int v, int val) {
		if (u > r or v < l) return;
		if (u <= l and r <= v) {
			st[id] = max(st[id], val);
			lazy[id] = max(lazy[id], val);
			return;
		}
		pushx(id);
		int mid = (l + r) >> 1;

		updatex(id << 1, l, mid, u, v, val);
		updatex(id << 1 | 1, mid + 1, r, u, v, val);
		st[id] = max(st[id << 1], st[id << 1 | 1]);
	}

	int getx (int id, int l, int r, int u, int v) {
		if (u > r or v < l) return 0;
		if (u <= l and r <= v) {
			return st[id];
		}
		pushx(id);
		int mid = (l + r) >> 1;

		return max(getx(id << 1, l, mid, u, v), getx(id << 1 | 1, mid + 1, r, u, v));
	}

	void buildn (int id, int l, int r) {
		st[id] = INF;
		lazy[id] = INF;
		if (l == r) return;

		int mid = (l + r) >> 1;
		buildn(id << 1, l, mid);
		buildn(id << 1 | 1, mid + 1, r);
	}

	void pushn (int id) {
		st[id << 1] = min(lazy[id], st[id << 1]);
		st[id << 1 | 1] = min(st[id << 1 | 1], lazy[id]);

		lazy[id << 1] = min(lazy[id << 1], lazy[id]);
		lazy[id << 1 | 1] = min(lazy[id << 1 | 1], lazy[id]);

		lazy[id] = INF;
	}

	void updaten (int id, int l, int r, int u, int v, int val) {
		if (u > r or v < l) return;
		if (u <= l and r <= v) {
			st[id] = min(st[id], val);
			lazy[id] = min(lazy[id], val);
			return;
		}
		pushn(id);
		int mid = (l + r) >> 1;

		updaten(id << 1, l, mid, u, v, val);
		updaten(id << 1 | 1, mid + 1, r, u, v, val);
		st[id] = min(st[id << 1], st[id << 1 | 1]);
	}

	int getn (int id, int l, int r, int u, int v) {
		if (u > r or v < l) return MOD;
		if (u <= l and r <= v) {
			return st[id];
		}
		pushn(id);
		int mid = (l + r) >> 1;

		return min(getn(id << 1, l, mid, u, v), getn(id << 1 | 1, mid + 1, r, u, v));
	}
} ST, ST1;

void update (int id, int l, int r, int pos, int val) {
	if (l == r) {
		st[id] = val;
		return;
	}
	int mid = (l + r) >> 1;

	if (pos <= mid) update(id << 1, l, mid, pos, val);
	else update(id << 1 | 1, mid + 1, r, pos, val);
	st[id] = max(st[id << 1], st[id << 1 | 1]);
}

int get (int id, int l, int r, int u, int v) {
	if (u > r or v < l) return 0;
	if (u <= l and r <= v) {
		return st[id];
	}
	int mid = (l + r) >> 1;

	return max(get(id << 1, l, mid, u, v), get(id << 1 | 1, mid + 1, r, u, v));
}

void solve() {
	cin >> n;
	FOR (i, 1, n) cin >> a[i].first;
	FOR (i, 1, n) cin >> a[i].second;

	kien q; cin >> q;
	FOR (i, 1, q) {
		int ll, rr;
		cin >> ll >> rr;
//		qr[r].pb({l, i});
		qr[ll].pb({rr, i});
	}

	FOR (i, 1, n) {
		l[i] = ST.getx(1, 1, 2 * n, a[i].second, a[i].first);
		ST.updatex(1, 1, 2 * n, a[i].second, a[i].first, i);
	}

	ST1.buildn(1, 1, 2 * n);
	FORD (i, n, 1) {
		r[i] = ST1.getn(1, 1, 2 * n, a[i].second, a[i].first);
		ST1.updaten(1, 1, 2 * n, a[i].second, a[i].first, i);
		vec[l[i]].pb(i);
	}

	FOR (i, 1, n) update(1, 1, n, i, r[i]);

	FORD (i, n, 1) {
		for (auto x : vec[i]) {
			update(1, 1, n, x, 0);
		}

		for (auto [R, id] : qr[i]) {
			if (get(1, 1, n, i, R) > R) ans[id] = 0;
			else ans[id] = 1;
		}
	}

	FOR (i, 1, q) if (ans[i]) cout << "Yes\n"; else cout << "No\n";
}

main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	if (fopen(task".inp", "r")) {
		fin(task); fou(task);
	}

	int tt = 1; // cin >> tt;
	while(tt--) {
		solve();
	}

	cerr << "\n" << 1.0 * clock() / CLOCKS_PER_SEC << "s ";
}

컴파일 시 표준 에러 (stderr) 메시지

Main.cpp:184:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  184 | main() {
      | ^~~~
Main.cpp: In function 'int main()':
Main.cpp:13:23: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   13 | #define fin(x) freopen(x".inp","r",stdin)
      |                ~~~~~~~^~~~~~~~~~~~~~~~~~~
Main.cpp:189:17: note: in expansion of macro 'fin'
  189 |                 fin(task); fou(task);
      |                 ^~~
Main.cpp:14:23: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   14 | #define fou(x) freopen(x".out","w",stdout)
      |                ~~~~~~~^~~~~~~~~~~~~~~~~~~~
Main.cpp:189:28: note: in expansion of macro 'fou'
  189 |                 fin(task); fou(task);
      |                            ^~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...