oj.uz

답안 #485066

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
485066 2021-11-06T02:25:13 Z socho Fire (JOI20_ho_t5) C++14
6 / 100
 227 ms 26660 KB 
/*
 Going for Subtask 4
*/
#include <bits/stdc++.h>
using namespace std;
void fast() {
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
}
void ran() {
	srand(chrono::steady_clock::now().time_since_epoch().count());
}
long long get_rand() {
	long long a = rand();
	long long b = rand();
	return a * (RAND_MAX + 1ll) + b;
}
void usaco() {
	freopen("problem.in", "r", stdin); 
	freopen("problem.out", "w", stdout);
}
template<typename T>
using min_pq = priority_queue<T, vector<T>, greater<T>>;
#define endl '\n'
// #define double long double
#define int long long
// const int MOD = 1000 * 1000 * 1000 + 7;
// const int MOD = 998244353;
// #define cerr if(0) cerr
#define debug(x) cerr << #x << ": " << x << endl;

int n, q;
const int MXN = 200005;
int arr[MXN];
int narr[MXN];
int seg[MXN * 4];

void build(int ind, int l, int r) {
	if (l == r) {
		seg[ind] = 1;
		return;
	}
	int m = (l + r) / 2;
	build(ind*2, l, m);
	build(ind*2+1, m+1, r);
	seg[ind] = (seg[ind*2] + seg[ind*2+1]);
}

void update(int ind, int l, int r, int pos, int to) {
	if (l == r) {
		seg[ind] = to;
		return;
	}
	int m = (l + r) / 2;
	if (pos <= m) update(ind*2, l, m, pos, to);
	else update(ind*2+1, m+1, r, pos, to);
	seg[ind] = seg[ind*2] + seg[ind*2+1];
}

int query(int ind, int l, int r, int ql, int qr) {
	if (ql <= l && r <= qr) return seg[ind];
	if (ql > r || qr < l) return 0;
	int m = (l + r) / 2;
	return (query(ind*2, l, m, ql, qr) + query(ind*2+1, m+1, r, ql, qr));
}

vector<int> positions[MXN];
int ans[MXN];

signed main() {

	ran(); fast();

	cin >> n >> q;
	for (int i=1; i<=n; i++) cin >> arr[i];
	
	build(1, 1, n);
	
	int latest = -n;
	for (int i=1; i<=n; i++) {
		if (arr[i] == 2) latest = i;
		positions[i - latest].push_back(i);
	}
	
	vector<pair<pair<int, int>, pair<int, int>>> proc;
	for (int i=0; i<q; i++) {
		int t, l, r;
		cin >> t >> l >> r;
		proc.push_back({{t, i}, {l, r}});
	}
	
	sort(proc.begin(), proc.end());
	
	int cr = 0;
	
	for (auto x: proc) {
		// answer this query
		int t = x.first.first, i = x.first.second, l = x.second.first, r = x.second.second;
		while (cr <= t) {
			for (auto j: positions[cr]) {
				update(1, 1, n, j, 2);
			}
			cr++;
		}
		ans[i] = query(1, 1, n, l, r);
	}
	
	for (int i=0; i<q; i++) cout << ans[i] << endl;

}

Compilation message

ho_t5.cpp: In function 'void usaco()':
ho_t5.cpp:18:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   18 |  freopen("problem.in", "r", stdin);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
ho_t5.cpp:19:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   19 |  freopen("problem.out", "w", stdout);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 1.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 4940 KB Output isn't correct

Subtask #2
0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 4940 KB Output isn't correct

Subtask #3
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 4940 KB Output isn't correct

Subtask #4
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 227 ms 21992 KB Output is correct
2 Correct 215 ms 26176 KB Output is correct
3 Correct 184 ms 26628 KB Output is correct
4 Correct 203 ms 26404 KB Output is correct
5 Correct 191 ms 26400 KB Output is correct
6 Correct 179 ms 25980 KB Output is correct
7 Correct 184 ms 26268 KB Output is correct
8 Correct 191 ms 26440 KB Output is correct
9 Correct 184 ms 25372 KB Output is correct
10 Correct 189 ms 25300 KB Output is correct
11 Correct 216 ms 26604 KB Output is correct
12 Correct 197 ms 26660 KB Output is correct
13 Correct 195 ms 26312 KB Output is correct
14 Correct 195 ms 26424 KB Output is correct

Subtask #5
0 / 80.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 4940 KB Output isn't correct