oj.uz

답안 #410794

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
410794 2021-05-23T18:17:41 Z nichke Cambridge (info1cup18_cambridge) C++14
0 / 100
 1 ms 332 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'

const int INF = 2e9;

int n, m;
int t[100005];
int d[100005];
int lz[400005];
int tmp[100005];
int lazy[400005];
int tree[400005];
int rmost[100005];

void push(int v, int l, int r) {
	if (l > r) return;
	if (lz[v] == 0) return;
	tree[v] += lazy[v];
	if (l != r) {
		lz[2 * v] = 1;
		lz[2 * v + 1] = 1;
		lazy[2 * v] += lazy[v];
		lazy[2 * v + 1] += lazy[v];
	}
	lazy[v] = 0;
	lz[v] = 0;
}

void update(int v, int tl, int tr, int ul, int ur, int val) {
	push(v, tl, tr);
	if (tl > ur || tr < ul || tl > tr) return;
	if (tl >= ul && tr <= ur) {
		lz[v] = 1;
		lazy[v] += val;
		push(v, tl, tr);
		return;
	}
	int tm = (tl + tr) / 2;
	update(2 * v, tl, tm, ul, ur, val);
	update(2 * v + 1, tm + 1, tr, ul, ur, val);
	tree[v] = max(tree[2 * v], tree[2 * v + 1]);
}

int query(int v, int tl, int tr, int ql, int qr) {
	push(v, tl, tr);
	if (tl > tr || tl > qr || tr < ql) {
		return -INF;
	}
	if (tl >= ql && tr <= qr) {
		return tree[v];
	}
	int tm = (tl + tr) / 2;
	return max(query(2 * v, tl, tm, ql, qr), query(2 * v + 1, tm + 1, tr, ql, qr));
}

void add(int v) {
	update(1, 1, n, tmp[v], tmp[v], INF - d[v]);
	update(1, 1, n, tmp[v], n, t[v]);
}

void remove(int v) {
	update(1, 1, n, tmp[v], tmp[v], -0x3f + d[v]);
	update(1, 1, n, tmp[v], n, -t[v]);
}

signed main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> m;
	vector<pair<int, int>> v;
	for (int i = 1; i <= n; i++) {
		cin >> t[i] >> d[i];
		v.push_back({d[i], i});
	}
	sort(v.begin(), v.end());
	for (int i = 0; i < v.size(); i++) {
		tmp[v[i].second] = i + 1;
	}
	int r = 0;
	update(1, 1, n, 1, n, -0x3f);
	for (int i = 1; i <= n; i++) {
		while (r <= n && query(1, 1, n, 1, n) < 0) {
			r++;
			if (r <= n) {
				add(r);
			}
		}
		remove(i);
		rmost[i] = r - 1;
	}
	for (int i = 0; i < m; i++) {
		int l, r; cin >> l >> r;
		if (rmost[l] >= r) {
			cout << 1 << '\n';
		} else {
			cout << 0 << '\n';
		}
	}
	return 0;
}

Compilation message

cambridge.cpp: In function 'int main()':
cambridge.cpp:78:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   78 |  for (int i = 0; i < v.size(); i++) {
      |                  ~~^~~~~~~~~~

Subtask #1
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 332 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 332 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 332 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 45.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 332 KB Output isn't correct
2 Halted 0 ms 0 KB -