oj.uz

Submission #681733

# Submission time Handle Problem Language Result Execution time Memory
681733 2023-01-14T00:46:16 Z NK_ Fortune Telling 2 (JOI14_fortune_telling2) C++17
4 / 100
 115 ms 13332 KB 
#include <bits/stdc++.h>

using namespace std;

#define nl '\n'

using ll = long long;

struct BIT {
	vector<int> data; int N;
	void init(int n) { N = n; data = vector<int>(N, 0); }
	void add(int p, int x) { for(++p;p<=N;p+=p&-p) data[p-1] += x; }
	int sum(int l, int r) { return sum(r+1) - sum(l); }
	int sum(int r) { int s = 0; for(;r;r-=r&-r) s += data[r-1]; return s; }
};

struct ST {
	int level(int x) { return 31 - __builtin_clz(x); }
	int comb(int a, int b) { return max(a, b); }
	vector<int> v; vector<vector<int>> jmp;
	void init(const vector<int> &_v) {
		v = _v; jmp = {v};
		for(int j = 1; (1<<j) <= size(v); j++) {
			jmp.push_back(vector<int>(size(v) - (1<<j) + 1));
			for(int i = 0; i < size(jmp[j]); i++) {
				jmp[j][i] = comb(jmp[j-1][i], jmp[j-1][i + (1<<(j-1))]);
			}	
		}
	}

	int query(int l, int r) {
		if (l > r) swap(l, r);
		int d = level(r - l + 1);
		return comb(jmp[d][l], jmp[d][r - (1<<d) + 1]);
	}
};

int main() {
	cin.tie(0)->sync_with_stdio(0);
	
	int N, Q; cin >> N >> Q;

	vector<int> A(N), B(N), T(Q);
	for(int i = 0; i < N; i++) cin >> A[i] >> B[i];
	for(int i = 0; i < Q; i++) cin >> T[i];

	vector<int> a = A, b = B;


	int M = -1;
	{
		map<int, int> mp; int cur = 0;
		for(auto x : A) mp[x]++;
		for(auto x : B) mp[x]++;
		for(auto x : T) mp[x]++;

		for(auto &p : mp) p.second = cur++;

		for(auto &x : a) x = mp[x];
		for(auto &x : b) x = mp[x];
		for(auto &x : T) x = mp[x];

		M = cur;
	}

	vector<int> ti(M, -1); for(int i = 0; i < Q; i++) ti[T[i]] = max(ti[T[i]], i);

	ST st; st.init(ti);

	vector<vector<int>> qry(Q);

	vector<int> S(N, 0);
	for(int i = 0; i < N; i++) {
		int time = st.query(a[i], b[i]);
		if (time != -1) S[i] = (a[i] >= b[i] ? 0 : 1);
		else time = 0;
		qry[time].push_back(i);
	}

	ll ans = 0;

	BIT F; F.init(M);
	for(int i = Q - 1; i >= 0; i--) {
		F.add(T[i], 1);

		for(auto x : qry[i]) {
			int mx = max(a[x], b[x]);
			int amt = F.sum(mx, M-1);

			S[x] ^= (amt % 2);
			// cout << x << " " << S[x] << nl;

			if (S[x]) ans += B[x];
			else ans += A[x];
			// cout << ans << nl;
		}	
	}	


	cout << ans << nl;

    return 0;
}

Compilation message

fortune_telling2.cpp: In member function 'void ST::init(const std::vector<int>&)':
fortune_telling2.cpp:23:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   23 |   for(int j = 1; (1<<j) <= size(v); j++) {
      |                  ~~~~~~~^~~~~~~~~~
fortune_telling2.cpp:25:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   25 |    for(int i = 0; i < size(jmp[j]); i++) {
      |                   ~~^~~~~~~~~~~~~~

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 2 ms 468 KB Output is correct
4 Correct 2 ms 460 KB Output is correct
5 Correct 2 ms 468 KB Output is correct
6 Correct 2 ms 468 KB Output is correct
7 Correct 2 ms 468 KB Output is correct
8 Correct 2 ms 496 KB Output is correct
9 Correct 1 ms 468 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 468 KB Output is correct
12 Correct 2 ms 468 KB Output is correct
13 Correct 2 ms 468 KB Output is correct

Subtask #2
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 2 ms 468 KB Output is correct
4 Correct 2 ms 460 KB Output is correct
5 Correct 2 ms 468 KB Output is correct
6 Correct 2 ms 468 KB Output is correct
7 Correct 2 ms 468 KB Output is correct
8 Correct 2 ms 496 KB Output is correct
9 Correct 1 ms 468 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 468 KB Output is correct
12 Correct 2 ms 468 KB Output is correct
13 Correct 2 ms 468 KB Output is correct
14 Correct 20 ms 3340 KB Output is correct
15 Correct 38 ms 6392 KB Output is correct
16 Correct 58 ms 9296 KB Output is correct
17 Correct 96 ms 12832 KB Output is correct
18 Correct 85 ms 13248 KB Output is correct
19 Correct 85 ms 13332 KB Output is correct
20 Correct 115 ms 13052 KB Output is correct
21 Correct 80 ms 12836 KB Output is correct
22 Correct 50 ms 8892 KB Output is correct
23 Incorrect 46 ms 7340 KB Output isn't correct
24 Halted 0 ms 0 KB -

Subtask #3
0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 2 ms 468 KB Output is correct
4 Correct 2 ms 460 KB Output is correct
5 Correct 2 ms 468 KB Output is correct
6 Correct 2 ms 468 KB Output is correct
7 Correct 2 ms 468 KB Output is correct
8 Correct 2 ms 496 KB Output is correct
9 Correct 1 ms 468 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 468 KB Output is correct
12 Correct 2 ms 468 KB Output is correct
13 Correct 2 ms 468 KB Output is correct
14 Correct 20 ms 3340 KB Output is correct
15 Correct 38 ms 6392 KB Output is correct
16 Correct 58 ms 9296 KB Output is correct
17 Correct 96 ms 12832 KB Output is correct
18 Correct 85 ms 13248 KB Output is correct
19 Correct 85 ms 13332 KB Output is correct
20 Correct 115 ms 13052 KB Output is correct
21 Correct 80 ms 12836 KB Output is correct
22 Correct 50 ms 8892 KB Output is correct
23 Incorrect 46 ms 7340 KB Output isn't correct
24 Halted 0 ms 0 KB -