제출 #1258883

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1258883		_rain_	운세 보기 2 (JOI14_fortune_telling2)	C++20	0 / 100	1 ms	576 KiB

fortune_telling2

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

#define FOR(i,a,b) for(int i = (a) , _b = (b); i <= _b; ++i)
#define MASK(x) ((LL)(1)<<(x))
#define BIT(mask , x) (((mask)>>x)&(1))
#define sz(x) (int)(x).size()

template<class X,class Y>	
	bool maximize(X &x , Y y){
		if (x < y) return x = y , true; else return false;
	}
template<class X,class Y>
	bool minimize(X &x , Y y){
		if (x > y) return x = y , true; else return false;
	}
template<class T>
	void compress(vector<T>&data){
		sort(data.begin() , data.end());
		data.resize(unique(data.begin() , data.end()) - data.begin());
	}
template<class X,class Y>
	int Find(vector<X>&data,Y y){
		return upper_bound(data.begin() , data.end() , y) - data.begin();
	}

const int N = (int) 200000;
const int MAXLOG = (int)19;
	int a[N + 2] , b[N + 2] , t[N + 2];
	int rmq[N*2 + 2][MAXLOG + 2];
	int LOG[N*2+2];
	
	int n , k;
	vector<int>v;
	int limit_size = 0;
	
	struct Node{
		int pos;
		int x , y;
		bool operator < (const Node&other) const{
			return pos > other.pos;
		}
	};
	
	int Get_max_index(int l , int r){
		int x = LOG[r - l + 1];
		return max(rmq[l][x] , rmq[r - MASK(x) + 1][x]);
	}
	
	int bit[N + 2];
		void upd(int pos , int val){
			for(;pos; pos -= pos&-pos) bit[pos] += val;
			return;
		}
		int Get(int pos){
			int sum = 0;
			for(;pos <= limit_size;pos += pos&-pos) sum+=bit[pos];
			return sum;
		}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0) ; cout.tie(0) ;
	#define name "main"
		if (fopen(name".inp","r")){
			freopen(name".inp","r",stdin);
			freopen(name".out","w",stdout);
		}
		
		cin >> n >> k;
		for(int i = 1; i <= n; ++i) {
			cin >> a[i] >> b[i];
			v.push_back(a[i]) , v.push_back(b[i]);
		}
		for(int i = 1; i <= k; ++i){
			cin >> t[i];
			v.push_back(t[i]);
		}
		compress(v);
		limit_size = sz(v);
		for(int i = 1; i <= k; ++i) {
			t[i] = Find(v , t[i]);
			maximize(rmq[t[i]][0] , i);
		}
			
			FOR(i,2,n+k) LOG[i] = LOG[i/2] + 1;
			FOR(j,1,MAXLOG){
				for(int i = 1; i <= limit_size - MASK(j) + 1; ++i){
					rmq[i][j] = max(rmq[i][j - 1] , rmq[i + MASK(j - 1)][j - 1]);
				}
			}
		
		vector<Node>events;
		for(int i = 1; i <= n; ++i){
			a[i] = Find(v , a[i]) , b[i] = Find(v , b[i]);
			int mx = max(a[i] , b[i]) ,  mn  = min(a[i] , b[i]);
			int last_index_change = Get_max_index(mn , mx - 1);
			if (last_index_change == 0) events.push_back({last_index_change , a[i] , b[i]});
				else events.push_back({last_index_change , mx , mn});
		}
		sort(events.begin() , events.end());
		int i = k;
		LL ans = 0;
		for(auto& id : events){
			while (i > id.pos) upd(t[i--] , 1);
			int numsteps = Get(id.x);
			if (numsteps%2==0) ans += v[id.x-1];
				else ans += v[id.y-1];
		}
		cout << ans;
}

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

fortune_telling2.cpp: In function 'int main()':
fortune_telling2.cpp:67:32: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   67 |                         freopen(name".inp","r",stdin);
      |                         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
fortune_telling2.cpp:68:32: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   68 |                         freopen(name".out","w",stdout);
      |                         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

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