Submission #274052

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
274052	2020-08-19T08:19:59 Z	Falcon	Fortune Telling 2 (JOI14_fortune_telling2)	C++14	35 / 100	777 ms	262148 KB

fortune_telling2

#pragma GCC optimize("O2")

#include <bits/stdc++.h>
#ifdef DEBUG
    #include "debug.hpp"
#endif

using namespace std;

#define all(c) (c).begin(), (c).end()
#define traverse(c, it) for(auto it = (c).begin(); it != (c).end(); it++)
#define rep(i, N) for(int i = 0; i < (N); i++)
#define rep1(i, N) for(int i = 1; i <= (N); i++)
#define rep2(i, s, e) for(int i = (s); i <= (e); i++)
#define rep3(i, s, e, d) for(int i = (s); (d) >= 0 ? i <= (e) : i >= (e); i += (d))
#define pb push_back


#ifdef DEBUG
    #define debug(x...) {dbg::depth++; string dbg_vals = dbg::to_string(x); dbg::depth--; dbg::fprint(__func__, __LINE__, #x, dbg_vals);}
    #define light_debug(x) {dbg::light = 1; dbg::dout << __func__ << ":" << __LINE__ << "  " << #x << " = " << x << endl; dbg::light = 0;}
#else
    #define debug(x...)
    #define light_debug(x) 
#endif

template<typename T>
T& ckmin(T& a, T b){ return a = a > b ? b : a; }

template<typename T>
T& ckmax(T& a, T b){ return a = a < b ? b : a; }

using ll = long long;
using pii = pair<int, int>;
using vi = vector<int>;

class Compress{
	vi vals;

public:
	inline int rank(int x) const{
		return lower_bound(all(vals), x) - vals.begin();
	}

	Compress(vi& v){
		vals = v;
		sort(all(vals));
		vals.erase(unique(all(vals)), vals.end());
		for(auto& x : v) x = rank(x);
	}

	inline int size() const{
		return vals.size();
	}
};


class segtree{
	int n;
	vi seg;

	inline void pull(int i){
		seg[i] = max(seg[i << 1], seg[i << 1 | 1]);
	}

public:
	inline segtree(int _n){
		n = _n;
		seg.resize(n << 1);
		fill(all(seg), -1);
	}

	void update(int i, int v){
		for(ckmax(seg[i += n], v), i >>= 1; i; i >>= 1)
			pull(i);
	}

	// [s, e)
	int query(int s, int e) const{
		int m = -1;
		for(s += n, e += n; s < e; s >>= 1, e >>= 1){
			if(s & 1) ckmax(m, seg[s++]);
			if(e & 1) ckmax(m, seg[--e]);
		}
		return m;
	}
};

/*
class BIT{
	int n;
	vi a;

	void upd(int i, int v){
		for(i++; i <= n; i += i & -i)
			a[i] += v;
	}

public:
	inline BIT(int _n){
		n = _n;
		a.resize(n + 1);
	}

	inline void rupd(int l, int r){
		upd(l, 1), upd(r, -1);
	}

	int qry(int i) const{
		int s = 0;
		for(i++; i; i -= i & -i)
			s += a[i];
		return s;
	}
};
*/

class dynamicSegtree2D{ // I had to change this to Fenwick...

	class segtree1D{
		int n;
		struct node{
			int v = 0;
			node* l = 0;
			node* r = 0;
		};

		using pnode = node*;
		
		pnode root = 0;

		void update(pnode& t, int s, int e, int i, int v){
			if(i < s || e < i) return;
			if(!t) t = new node();
			t->v += v;
			debug(s, e, i, v, t->v);

			if(s != e)
				update(t->l, s, (s + e) >> 1, i, v), update(t->r, (s + e + 2) >> 1, e, i, v);
			
		}

		// [s, e]
		int query(pnode t, int s, int e, int l, int r){
			if(!t || r < s || e < l) return 0;
			debug(s, e, l, r, t->v);
			if(l <= s && e <= r) return t->v;
			else return query(t->l, s, (s + e) >> 1, l, r) + query(t->r, (s + e + 2) >> 1, e, l, r);
		}

	public:
		inline segtree1D(int _n = 0){ n = _n; }

		inline void update(int i, int v){ update(root, 0, n - 1, i, v); }

		inline int query(int l, int r){ return query(root, 0, n - 1, l, r); }

	};

	int n, k;
	vector<segtree1D> BIT;

	int pref(int i, int s, int e){
		int ans = 0;
		for(i++; i > 0; i -= i & -i)
			ans += BIT[i].query(s, e);
		return ans;
	}

public:
	inline dynamicSegtree2D(int _n, int _k){ n = _n; k = _k; BIT = vector<segtree1D>(n + 1, segtree1D(k)); }
	
	/*
	void update(int i, int j, int v){
		debug(i, j, v);
		for(i += n; i; i >>= 1){
			debug(i, j);
			seg[i].update(j, v);
		}
	}
	*/

	void update(int i, int j, int v){
		for(i++; i <= n; i += i & -i)
			BIT[i].update(j, v);
	}
	/*
	// [s1, e1], [s2, e2] and (1 -> index, 2 -> value)
	int query(int s1, int e1, int s2, int e2){
		int ans = 0;
		for(s1 += n, e1 += n + 1; s1 < e1; s1 >>= 1, e1 >>= 1){
			if(s1 & 1) {
				debug(s1, s2, e2, seg[s1].query(s2, e2));
				ans += seg[s1++].query(s2, e2);
			}
			if(e1 & 1) {
				debug(e1, seg[e1 - 1].query(s2, e2));
				ans += seg[--e1].query(s2, e2);
			}
		}
		return ans;
	}
	*/

	int query(int s1, int e1, int s2, int e2){
		return pref(e1, s2, e2) - pref(s1 - 1, s2, e2);
	}
};


signed main(){

    ios_base::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    #ifdef DEBUG
        freopen("debug", "w", stderr);
    #endif
    
    int N, K;
    cin >> N >> K;
    vi A(N), B(N), T(K);
    rep(i, N) cin >> A[i] >> B[i];
    rep(i, K) cin >> T[i];

    Compress compress(T);
    segtree seg(compress.size());
    dynamicSegtree2D seg2(K, compress.size());

    debug(T);
    rep(i, K) {
    	seg.update(T[i], i);
    	seg2.update(i, T[i], 1);
    }

    debug(seg2.query(0, K - 1, 1, compress.size() - 1));

    rep(i, N){
    	int l = compress.rank(A[i]);
    	int r = compress.rank(B[i]);
    	if(l > r) swap(l, r);
    	int t = seg.query(l, r);
    	if(t != -1 && A[i] < B[i]) swap(A[i], B[i]);
    	int k = seg2.query(t + 1, K - 1, r, compress.size() - 1);
    	debug(i, l, r, t, k);
    	if(k & 1) swap(A[i], B[i]);
    }

    cout << accumulate(all(A), 0LL) << '\n';

    #ifdef DEBUG
        dbg::dout << "\nExecution time: " << clock() << "ms\n";
    #endif

    return 0;
}

Subtask #1

4.0 / 4.0

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

Subtask #2

31.0 / 31.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	1408 KB	Output is correct
2	Correct	4 ms	1408 KB	Output is correct
3	Correct	6 ms	1408 KB	Output is correct
4	Correct	6 ms	1408 KB	Output is correct
5	Correct	4 ms	1408 KB	Output is correct
6	Correct	4 ms	1408 KB	Output is correct
7	Correct	5 ms	1408 KB	Output is correct
8	Correct	4 ms	1408 KB	Output is correct
9	Correct	4 ms	1408 KB	Output is correct
10	Correct	3 ms	1280 KB	Output is correct
11	Correct	4 ms	1408 KB	Output is correct
12	Correct	5 ms	1408 KB	Output is correct
13	Correct	4 ms	1408 KB	Output is correct
14	Correct	77 ms	18808 KB	Output is correct
15	Correct	150 ms	42268 KB	Output is correct
16	Correct	270 ms	66904 KB	Output is correct
17	Correct	352 ms	94456 KB	Output is correct
18	Correct	330 ms	94424 KB	Output is correct
19	Correct	321 ms	94332 KB	Output is correct
20	Correct	346 ms	94328 KB	Output is correct
21	Correct	311 ms	94328 KB	Output is correct
22	Correct	263 ms	89592 KB	Output is correct
23	Correct	264 ms	88696 KB	Output is correct
24	Correct	249 ms	87492 KB	Output is correct
25	Correct	263 ms	90704 KB	Output is correct
26	Correct	312 ms	89336 KB	Output is correct
27	Correct	356 ms	91512 KB	Output is correct
28	Correct	293 ms	87800 KB	Output is correct
29	Correct	350 ms	94328 KB	Output is correct

Subtask #3

0 / 65.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	1408 KB	Output is correct
2	Correct	4 ms	1408 KB	Output is correct
3	Correct	6 ms	1408 KB	Output is correct
4	Correct	6 ms	1408 KB	Output is correct
5	Correct	4 ms	1408 KB	Output is correct
6	Correct	4 ms	1408 KB	Output is correct
7	Correct	5 ms	1408 KB	Output is correct
8	Correct	4 ms	1408 KB	Output is correct
9	Correct	4 ms	1408 KB	Output is correct
10	Correct	3 ms	1280 KB	Output is correct
11	Correct	4 ms	1408 KB	Output is correct
12	Correct	5 ms	1408 KB	Output is correct
13	Correct	4 ms	1408 KB	Output is correct
14	Correct	77 ms	18808 KB	Output is correct
15	Correct	150 ms	42268 KB	Output is correct
16	Correct	270 ms	66904 KB	Output is correct
17	Correct	352 ms	94456 KB	Output is correct
18	Correct	330 ms	94424 KB	Output is correct
19	Correct	321 ms	94332 KB	Output is correct
20	Correct	346 ms	94328 KB	Output is correct
21	Correct	311 ms	94328 KB	Output is correct
22	Correct	263 ms	89592 KB	Output is correct
23	Correct	264 ms	88696 KB	Output is correct
24	Correct	249 ms	87492 KB	Output is correct
25	Correct	263 ms	90704 KB	Output is correct
26	Correct	312 ms	89336 KB	Output is correct
27	Correct	356 ms	91512 KB	Output is correct
28	Correct	293 ms	87800 KB	Output is correct
29	Correct	350 ms	94328 KB	Output is correct
30	Runtime error	777 ms	262148 KB	Execution killed with signal 9
31	Halted	0 ms	0 KB	-