제출 #56738

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
56738		Mamnoon_Siam	운세 보기 2 (JOI14_fortune_telling2)	C++17	100 / 100	1042 ms	57060 KiB

fortune_telling2

#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;
	}
};
struct Tree {
	vector<vector<int>> t;
	Tree() {}
	Tree(vector<int> &vec) {
		t.resize(vec.size() << 2);
		build(1, 0, vec.size() - 1, vec);
	}
	void build(int u, int b, int e, vector<int> &vec) {
		for(int i = b; i <= e; i++) t[u].push_back(vec[i]);
		sort(all(t[u]));
		if(b == e) return;
		int mid = b + e >> 1;
		build(u << 1, b, mid, vec);
		build(u << 1 | 1, mid + 1, e, vec);
	}
	int query(int u, int b, int e, int i, int j, int x) {
		if(b > j or e < i) return 0;
		if(i <= b and e <= j) return t[u].end() - lower_bound(all(t[u]), x);
		int mid = b + e >> 1;
		return query(u << 1, b, mid, i, j, x) + query(u << 1 | 1, mid + 1, e, i, j, x);
	}
	int query(int l, int r, int x) {
		return query(1, 0, (t.size() >> 2) - 1, l, r, x);
	}
};

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

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

	MaxSegTree ds(mp.size() + 10);
	Tree tree(T);

	for(int i = 0; i < q; i++) ds.update(T[i], 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];
		int tog = tree.query(it, q - 1, B[i]);
		if(tog & 1) now ^= A[i] ^ B[i];
		ans += mp[now];
	} cout << ans << endl;
}

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

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;
                          ^~~
fortune_telling2.cpp: In member function 'void Tree::build(int, int, int, std::vector<int>&)':
fortune_telling2.cpp:63:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int mid = b + e >> 1;
             ~~^~~
fortune_telling2.cpp: In member function 'int Tree::query(int, int, int, int, int, int)':
fortune_telling2.cpp:70:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int mid = b + e >> 1;
             ~~^~~

• Subtask 1: 4 / 4
• Subtask 2: 31 / 31
• Subtask 3: 65 / 65