Submission #149141

#	Time	Username	Problem	Language	Result	Execution time	Memory
149141		팀명못정해서15시간째고민중인팀 (#200)	Crosses on the Grid (FXCUP4_cross)	C++17	100 / 100	259 ms	6764 KiB

cross

#include "cross.h"
#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
#define X first
#define Y second

pii A[200009];
int F[200009];
vector<int> X;

void upd(int x, int y) {
    for(int i=x; i<=X.size(); i+=(i&-i)) F[i] += y;
}

int get(int x) {
    int s = 0;
    for(int i=x; i>=1; i-=(i&-i)) s += F[i];
    return s;
}

int getx(int x) {
    return lower_bound(X.begin(), X.end(), x) - X.begin() + 1;
}

long long SelectCross(int K, vector<int> I, vector<int> O) {
	int N = I.size();
	for(int i=0; i<N; i++) {
        A[i] = {I[i], O[i]};
        X.push_back(O[i]);
	}
	sort(A, A+N); reverse(A, A+N);
	sort(X.begin(), X.end()); X.resize(unique(X.begin(), X.end()) - X.begin());
	long long ans = 0;
	for(int i=0; i<N; i++) {
        upd(getx(A[i].Y), +1);
        if(i+1 >= K) {
            int l = 0, r = X.size();
            while(l <= r) {
                int m = l+r >> 1;
                if(i+1 - get(m) >= K) {
                    ans = max(ans, (2LL*X[m] - A[i].X) * A[i].X);
                    l = m+1;
                }
                else r = m-1;
            }
        }
	}
	return ans;
}

Compilation message (stderr)

cross.cpp: In function 'void upd(int, int)':
cross.cpp:13:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=x; i<=X.size(); i+=(i&-i)) F[i] += y;
                  ~^~~~~~~~~~
cross.cpp: In function 'long long int SelectCross(int, std::vector<int>, std::vector<int>)':
cross.cpp:40:26: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
                 int m = l+r >> 1;
                         ~^~

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