제출 #1167776

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1167776		nguyn	운세 보기 2 (JOI14_fortune_telling2)	C++20	100 / 100	293 ms	47836 KiB

fortune_telling2

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

#define int long long 
#define ll long long 
#define F first
#define S second
#define pb push_back 
#define pii pair<int,int>

const int N = 2e5 + 5;

struct SegTree {
	vector<int> st;
	int n; 

	SegTree(int n) : n(n) {
		st.resize(4 * n + 5); 
	} 

	void update(int id, int l, int r, int i, int x) {
		if (i < l || i > r) return;
		if (l == r) {
			st[id] = x; 
			return;
		}
		int mid = (l + r) >> 1;
		update(id * 2, l, mid, i, x);
		update(id * 2 + 1, mid + 1, r, i, x);
		st[id] = max(st[id * 2], st[id * 2 + 1]); 
	}

	int get(int id, int l, int r, int u, int v) {
		if (u > v) {
			return 0;
		}
		if (u > r || v < l) return 0; 
		if (u <= l && r <= v) {
			return st[id]; 
		}
		int mid = (l + r) >> 1; 
		return max(get(id * 2, l, mid, u, v), get(id * 2 + 1, mid + 1, r, u, v));
	}
};

struct BIT {
	int n;
	vector<int> bit; 

	BIT(int n) : n(n) {
		bit.resize(n + 3); 
	}

	void update(int id, int val) {
		for (int i = id; i <= n; i += (i & -i)) bit[i] += val; 
	}

	int get(int id) {
		int res = 0;
		for (int i = id; i; i -= (i & -i)) res += bit[i]; 
		return res; 
	}
};

int n, q;
pii a[N]; 
pii b[N]; 
vector<int> cmp; 
int t[N]; 
int last[N];
int cnt[N];
vector<int> event[N];  

signed main(){
    ios_base::sync_with_stdio(false) ; 
    cin.tie(0) ; cout.tie(0) ; 
    if (fopen("INP.INP" ,"r")) {
        freopen("INP.INP" ,"r" , stdin) ;
        freopen("OUT.OUT" , "w" , stdout) ;
    }
    cin >> n >> q;
    for (int i = 1; i <= n; i++) {
    	cin >> a[i].F >> a[i].S; 
    	cmp.pb(a[i].F); 
    	cmp.pb(a[i].S); 
    }	
    for (int i = 1; i <= q; i++) {
    	cin >> t[i]; 
    	cmp.pb(t[i]); 
    }
    sort(cmp.begin(), cmp.end());
    cmp.erase(unique(cmp.begin(), cmp.end()), cmp.end()); 
    for (int i = 1; i <= n; i++) {
    	b[i].F = upper_bound(cmp.begin(), cmp.end(), a[i].F) - cmp.begin();
    	b[i].S = upper_bound(cmp.begin(), cmp.end(), a[i].S) - cmp.begin();
    	if (b[i].F > b[i].S) swap(b[i].F, b[i].S); 
    }
    for (int i = 1; i <= q; i++) {
    	t[i] = upper_bound(cmp.begin(), cmp.end(), t[i]) - cmp.begin();
    }
    int sz = cmp.size();
    SegTree st(sz); 
    for (int i = 1; i <= q; i++) {
    	st.update(1, 1, sz, t[i], i); 
    }
    for (int i = 1; i <= n; i++) {
    	last[i] = st.get(1, 1, sz, b[i].F, b[i].S - 1); 
    	event[last[i]].pb(i); 
    }
    BIT bit(sz); 
    for (int i = q; i >= 0; i--) {
    	// cout << i << ' ' << t[i] << endl; 
    	for (auto j : event[i]) {
    		// cout << j << ' '; 
    		cnt[j] = bit.get(sz) - bit.get(b[j].S - 1); 
    	} //cout << '\n'; 
    	if (i) bit.update(t[i], 1); 
    }
    int res = 0; 
    for (int i = 1; i <= n; i++) {
    	if (last[i]) {
    		int cur = max(a[i].F, a[i].S); 
    		if (cnt[i] & 1) cur = min(a[i].F, a[i].S); 
    		res += cur; 
    	}
    	else {
    		int cur = a[i].F; 	
    		if (cnt[i] & 1) cur = a[i].S; 
    		res += cur; 
    	}
    }
    cout << res;
}		

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

fortune_telling2.cpp: In function 'int main()':
fortune_telling2.cpp:78:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   78 |         freopen("INP.INP" ,"r" , stdin) ;
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
fortune_telling2.cpp:79:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   79 |         freopen("OUT.OUT" , "w" , stdout) ;
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

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