Submission #273988

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
273988	2020-08-19T08:05:21 Z	Falcon	Fortune Telling 2 (JOI14_fortune_telling2)	C++14	35 / 100	654 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{

	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> seg;

public:
	inline dynamicSegtree2D(int _n, int _k){ n = _n; k = _k; seg = 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);
		}
	}

	// [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;
	}
};


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	6 ms	2560 KB	Output is correct
2	Correct	5 ms	2560 KB	Output is correct
3	Correct	6 ms	2560 KB	Output is correct
4	Correct	5 ms	2560 KB	Output is correct
5	Correct	5 ms	2560 KB	Output is correct
6	Correct	6 ms	2560 KB	Output is correct
7	Correct	6 ms	2560 KB	Output is correct
8	Correct	6 ms	2560 KB	Output is correct
9	Correct	5 ms	2560 KB	Output is correct
10	Correct	5 ms	2304 KB	Output is correct
11	Correct	6 ms	2432 KB	Output is correct
12	Correct	6 ms	2432 KB	Output is correct
13	Correct	6 ms	2560 KB	Output is correct

Subtask #2

31.0 / 31.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	6 ms	2560 KB	Output is correct
2	Correct	5 ms	2560 KB	Output is correct
3	Correct	6 ms	2560 KB	Output is correct
4	Correct	5 ms	2560 KB	Output is correct
5	Correct	5 ms	2560 KB	Output is correct
6	Correct	6 ms	2560 KB	Output is correct
7	Correct	6 ms	2560 KB	Output is correct
8	Correct	6 ms	2560 KB	Output is correct
9	Correct	5 ms	2560 KB	Output is correct
10	Correct	5 ms	2304 KB	Output is correct
11	Correct	6 ms	2432 KB	Output is correct
12	Correct	6 ms	2432 KB	Output is correct
13	Correct	6 ms	2560 KB	Output is correct
14	Correct	80 ms	36856 KB	Output is correct
15	Correct	189 ms	83192 KB	Output is correct
16	Correct	304 ms	132896 KB	Output is correct
17	Correct	458 ms	186616 KB	Output is correct
18	Correct	459 ms	186488 KB	Output is correct
19	Correct	444 ms	186488 KB	Output is correct
20	Correct	494 ms	186492 KB	Output is correct
21	Correct	428 ms	186360 KB	Output is correct
22	Correct	430 ms	177400 KB	Output is correct
23	Correct	407 ms	175648 KB	Output is correct
24	Correct	466 ms	172920 KB	Output is correct
25	Correct	435 ms	179576 KB	Output is correct
26	Correct	441 ms	177016 KB	Output is correct
27	Correct	490 ms	181240 KB	Output is correct
28	Correct	401 ms	173560 KB	Output is correct
29	Correct	581 ms	186360 KB	Output is correct

Subtask #3

0 / 65.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	6 ms	2560 KB	Output is correct
2	Correct	5 ms	2560 KB	Output is correct
3	Correct	6 ms	2560 KB	Output is correct
4	Correct	5 ms	2560 KB	Output is correct
5	Correct	5 ms	2560 KB	Output is correct
6	Correct	6 ms	2560 KB	Output is correct
7	Correct	6 ms	2560 KB	Output is correct
8	Correct	6 ms	2560 KB	Output is correct
9	Correct	5 ms	2560 KB	Output is correct
10	Correct	5 ms	2304 KB	Output is correct
11	Correct	6 ms	2432 KB	Output is correct
12	Correct	6 ms	2432 KB	Output is correct
13	Correct	6 ms	2560 KB	Output is correct
14	Correct	80 ms	36856 KB	Output is correct
15	Correct	189 ms	83192 KB	Output is correct
16	Correct	304 ms	132896 KB	Output is correct
17	Correct	458 ms	186616 KB	Output is correct
18	Correct	459 ms	186488 KB	Output is correct
19	Correct	444 ms	186488 KB	Output is correct
20	Correct	494 ms	186492 KB	Output is correct
21	Correct	428 ms	186360 KB	Output is correct
22	Correct	430 ms	177400 KB	Output is correct
23	Correct	407 ms	175648 KB	Output is correct
24	Correct	466 ms	172920 KB	Output is correct
25	Correct	435 ms	179576 KB	Output is correct
26	Correct	441 ms	177016 KB	Output is correct
27	Correct	490 ms	181240 KB	Output is correct
28	Correct	401 ms	173560 KB	Output is correct
29	Correct	581 ms	186360 KB	Output is correct
30	Runtime error	654 ms	262148 KB	Execution killed with signal 9
31	Halted	0 ms	0 KB	-