제출 #149082

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
149082		잉여로운 고3 (#200)	십자가 놓기 (FXCUP4_cross)	C++17	100 / 100	256 ms	14440 KiB

cross

#include <bits/stdc++.h>

#include "cross.h"

using namespace std;

typedef long long ll;
typedef pair <ll, ll> pll;

struct segtree{
	ll T[606060];
	
	void insert(ll p, ll s, ll e, ll v)
	{
		T[p] ++;
		if(s == e) return;
		else if(v <= (s + e >> 1)){
			insert(p << 1, s, s + e >> 1, v);
		}
		else{
			insert(p << 1 | 1, (s + e >> 1) + 1, e, v);
		}
	}
	
	ll getval(ll p, ll s, ll e, ll k)
	{
		if(s == e) return s;
		else if(k > T[p << 1 | 1]){
			return getval(p << 1, s, s + e >> 1, k - T[p << 1 | 1]);
		}
		else{
			return getval(p << 1 | 1, (s + e >> 1) + 1, e, k);
		}
	}
};

segtree T;
vector <pll> P;
vector <ll> X;
ll n, ans;

ll SelectCross(int k, vector<int> I, vector <int> O)
{
	ll i, x, y;
	
	n = I.size();
	
	for(i=0; i<n; i++){
		P.emplace_back(I[i], O[i]);
		X.push_back(O[i]);
	}
	
	sort(P.begin(), P.end(), [&](pll &pa, pll &pb){
		if(pa.first == pb.first) return pa.second < pb.second;
		else return pa.first > pb.first;
	});
	
	sort(X.begin(), X.end());
	X.erase(unique(X.begin(), X.end()), X.end());
	
	for(i=0; i<k-1; i++){
		x = lower_bound(X.begin(), X.end(), P[i].second) - X.begin();
		T.insert(1, 0, n - 1, x);
	}
	
	for(; i<n; i++){
		if(k > 1){
			y = T.getval(1, 0, n - 1, k - 1);
			y = X[y];
		}
		else y = 1e9;
		
		x = P[i].first; y = min(y, P[i].second);
		ans = max(ans, 2 * x * y - x * x);
		
		x = lower_bound(X.begin(), X.end(), P[i].second) - X.begin();
		T.insert(1, 0, n - 1, x);
	}
	
	return ans;
}

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

cross.cpp: In member function 'void segtree::insert(ll, ll, ll, ll)':
cross.cpp:17:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   else if(v <= (s + e >> 1)){
                 ~~^~~
cross.cpp:18:24: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
    insert(p << 1, s, s + e >> 1, v);
                      ~~^~~
cross.cpp:21:26: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
    insert(p << 1 | 1, (s + e >> 1) + 1, e, v);
                        ~~^~~
cross.cpp: In member function 'll segtree::getval(ll, ll, ll, ll)':
cross.cpp:29:31: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
    return getval(p << 1, s, s + e >> 1, k - T[p << 1 | 1]);
                             ~~^~~
cross.cpp:32:33: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
    return getval(p << 1 | 1, (s + e >> 1) + 1, e, k);
                               ~~^~~

• Subtask 1: 8 / 8
• Subtask 2: 55 / 55
• Subtask 3: 37 / 37