oj.uz

Submission #56732

# Submission time Handle Problem Language Result Execution time Memory
56732 2018-07-12T08:58:45 Z Mamnoon_Siam Fortune Telling 2 (JOI14_fortune_telling2) C++17
35 / 100
 3000 ms 131372 KB 
//#pragma GCC optimize("Ofast,unroll-loops,no-stack-protector")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

#include <bits/stdc++.h>
using namespace std;

#define debug(s) cout<< #s <<" = "<< s <<endl
#define all(v) (v).begin(), (v).end()
#define KeepUnique(v) (v).erase( unique(all(v)), v.end() )
#define MEMSET(a,val) memset(a, val, sizeof a)
#define PB push_back
#define endl '\n'
typedef long long ll;

inline int myrand(int l, int r) {
	int ret = rand(); ret <<= 15; ret ^= rand();
	if(ret < 0) ret = -ret; ret %= (r-l+1); ret += l;
	return ret;
}
template <typename F, typename S>
ostream& operator << (ostream& os, const pair< F, S>& p) {
    return os<<"(" <<p.first<<", "<<p.second<<")"; }

typedef pair<int, int> ii;
template<typename T> using min_pq =
	priority_queue<T, vector<T>, greater<T> >;

//int dx[] = {-1, +0, +1, +0};
//int dy[] = {+0, +1, +0, -1};

const int maxn = 200010;
const int inf = 2e9;

struct MaxSegTree {
	vector<int> t;
	MaxSegTree() {}
	MaxSegTree(int N) {t.assign(N << 1, -1);}
	void update(int p, int val) {
		p += (t.size() >> 1);
		t[p] = max(t[p], val);
		for(; p > 1; p >>= 1) t[p >> 1] = max(t[p], t[p ^ 1]);
	}
	int query(int l, int r) {
		r++;
		int ret = -inf;
		for(l += (t.size() >> 1), r += (t.size() >> 1); l < r; l >>= 1, r >>= 1) {
			if(l & 1) ret = max(ret, t[l++]);
			if(r & 1) ret = max(ret, t[--r]);
		} return ret;
	}
};

int n, q;
vector<int> A, B, T;
vector<int> mp;
int flag[maxn], Now[maxn], It[maxn];
vector<int> ft[maxn];

void insert(int p, int val) {
	p++;
	for(; p <= q; p += p & -p)
		ft[p].push_back(val);
}
int query(int p, int x) {
	int ret = 0;
	for(; p > 0; p -= p & -p)
		ret += ft[p].end() - lower_bound(all(ft[p]), x);
	return ret;
}
int query(int l, int r, int val) {
	if(l >= r or l >= q or r >= q) return 0;
	return query(r + 1, val) - query(l, val);	
}

int32_t main () {
	// freopen("in", "r", stdin);

// input
	cin >> n >> q;
	A.resize(n), B.resize(n), T.resize(q);
	for(int i = 0; i < n; i++) {
		cin >> A[i] >> B[i];
		if(A[i] > B[i]) swap(A[i], B[i]), flag[i] = 1;
	}
	for(int &b : T) cin >> b;
// end
	
// compress
	for(int i = 0; i < n; i++) {
		mp.push_back(A[i]);
		mp.push_back(B[i]);
	}
	for(int b : T) mp.push_back(b);
	sort(all(mp));
	KeepUnique(mp);
	for(int i = 0; i < n; i++) {
		A[i] = lower_bound(all(mp), A[i]) - mp.begin();
		B[i] = lower_bound(all(mp), B[i]) - mp.begin();
	}
	for(int &b : T) {
		b = lower_bound(all(mp), b) - mp.begin();
	}
// end

	// for(int i = 0; i < n; i++) cout << A[i] << ' ' << B[i] << endl;
	// for(int b : T) cout << b << endl;

	MaxSegTree ds(mp.size() + 10);
	for(int i = 0; i < q; i++) {
		ds.update(T[i], i);
		insert(i, T[i]);
	}
	for(int i = 0; i <= q; i++) {
		sort(all(ft[i]));
	}
	ll ans = 0;
	for(int i = 0; i < n; i++) {
		if(A[i] == B[i]) {
			ans += mp[A[i]];
			continue;
		}
		int it = ds.query(A[i], B[i] - 1) + 1, now;
		if(!it) now = flag[i] ? B[i] : A[i];
		else now = B[i];
		Now[i] = now, It[i] = it;
		int tog = 0;
		for(int j = it; j < q; j++)
			if(T[j] >= B[i]) tog++;
		// cout << it << ' ' << tog << endl;
		if(tog & 1) now ^= A[i] ^ B[i];
		ans += mp[now];
	} cout << ans << endl;
}

Compilation message

fortune_telling2.cpp: In function 'int myrand(int, int)':
fortune_telling2.cpp:17:2: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
  if(ret < 0) ret = -ret; ret %= (r-l+1); ret += l;
  ^~
fortune_telling2.cpp:17:26: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
  if(ret < 0) ret = -ret; ret %= (r-l+1); ret += l;
                          ^~~

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 5112 KB Output is correct
2 Correct 10 ms 5112 KB Output is correct
3 Correct 11 ms 5168 KB Output is correct
4 Correct 13 ms 5424 KB Output is correct
5 Correct 10 ms 5424 KB Output is correct
6 Correct 16 ms 5424 KB Output is correct
7 Correct 12 ms 5424 KB Output is correct
8 Correct 11 ms 5424 KB Output is correct
9 Correct 10 ms 5424 KB Output is correct
10 Correct 11 ms 5424 KB Output is correct
11 Correct 11 ms 5424 KB Output is correct
12 Correct 10 ms 5424 KB Output is correct
13 Correct 10 ms 5424 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 5112 KB Output is correct
2 Correct 10 ms 5112 KB Output is correct
3 Correct 11 ms 5168 KB Output is correct
4 Correct 13 ms 5424 KB Output is correct
5 Correct 10 ms 5424 KB Output is correct
6 Correct 16 ms 5424 KB Output is correct
7 Correct 12 ms 5424 KB Output is correct
8 Correct 11 ms 5424 KB Output is correct
9 Correct 10 ms 5424 KB Output is correct
10 Correct 11 ms 5424 KB Output is correct
11 Correct 11 ms 5424 KB Output is correct
12 Correct 10 ms 5424 KB Output is correct
13 Correct 10 ms 5424 KB Output is correct
14 Correct 45 ms 6364 KB Output is correct
15 Correct 98 ms 7540 KB Output is correct
16 Correct 164 ms 8588 KB Output is correct
17 Correct 173 ms 11108 KB Output is correct
18 Correct 173 ms 12200 KB Output is correct
19 Correct 201 ms 13604 KB Output is correct
20 Correct 200 ms 14672 KB Output is correct
21 Correct 194 ms 15740 KB Output is correct
22 Correct 130 ms 15988 KB Output is correct
23 Correct 153 ms 16524 KB Output is correct
24 Correct 148 ms 17096 KB Output is correct
25 Correct 148 ms 18224 KB Output is correct
26 Correct 929 ms 19156 KB Output is correct
27 Correct 1172 ms 20604 KB Output is correct
28 Correct 1196 ms 21848 KB Output is correct
29 Correct 2017 ms 23172 KB Output is correct

Subtask #3
0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 5112 KB Output is correct
2 Correct 10 ms 5112 KB Output is correct
3 Correct 11 ms 5168 KB Output is correct
4 Correct 13 ms 5424 KB Output is correct
5 Correct 10 ms 5424 KB Output is correct
6 Correct 16 ms 5424 KB Output is correct
7 Correct 12 ms 5424 KB Output is correct
8 Correct 11 ms 5424 KB Output is correct
9 Correct 10 ms 5424 KB Output is correct
10 Correct 11 ms 5424 KB Output is correct
11 Correct 11 ms 5424 KB Output is correct
12 Correct 10 ms 5424 KB Output is correct
13 Correct 10 ms 5424 KB Output is correct
14 Correct 45 ms 6364 KB Output is correct
15 Correct 98 ms 7540 KB Output is correct
16 Correct 164 ms 8588 KB Output is correct
17 Correct 173 ms 11108 KB Output is correct
18 Correct 173 ms 12200 KB Output is correct
19 Correct 201 ms 13604 KB Output is correct
20 Correct 200 ms 14672 KB Output is correct
21 Correct 194 ms 15740 KB Output is correct
22 Correct 130 ms 15988 KB Output is correct
23 Correct 153 ms 16524 KB Output is correct
24 Correct 148 ms 17096 KB Output is correct
25 Correct 148 ms 18224 KB Output is correct
26 Correct 929 ms 19156 KB Output is correct
27 Correct 1172 ms 20604 KB Output is correct
28 Correct 1196 ms 21848 KB Output is correct
29 Correct 2017 ms 23172 KB Output is correct
30 Correct 481 ms 36240 KB Output is correct
31 Correct 594 ms 40916 KB Output is correct
32 Correct 653 ms 46996 KB Output is correct
33 Correct 962 ms 57024 KB Output is correct
34 Correct 409 ms 57024 KB Output is correct
35 Correct 1010 ms 64724 KB Output is correct
36 Correct 954 ms 70588 KB Output is correct
37 Correct 1095 ms 76340 KB Output is correct
38 Correct 1033 ms 82172 KB Output is correct
39 Correct 981 ms 87976 KB Output is correct
40 Correct 1002 ms 93696 KB Output is correct
41 Correct 955 ms 99532 KB Output is correct
42 Correct 1062 ms 105288 KB Output is correct
43 Correct 817 ms 109736 KB Output is correct
44 Correct 731 ms 114892 KB Output is correct
45 Correct 693 ms 119904 KB Output is correct
46 Correct 705 ms 121524 KB Output is correct
47 Correct 1059 ms 124680 KB Output is correct
48 Execution timed out 3047 ms 131372 KB Time limit exceeded
49 Halted 0 ms 0 KB -