oj.uz

Submission #149082

# Submission time Handle Problem Language Result Execution time Memory
149082 2019-09-01T05:42:47 Z 잉여로운 고3(#3749, imyujin, sebinkim) Crosses on the Grid (FXCUP4_cross) C++17
100 / 100
 256 ms 14440 KB 
#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;
}

Compilation message

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.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 128 KB Output is correct
2 Correct 5 ms 128 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 6 ms 384 KB Output is correct
5 Correct 15 ms 1148 KB Output is correct
6 Correct 203 ms 14432 KB Output is correct
7 Correct 199 ms 14344 KB Output is correct
8 Correct 205 ms 14428 KB Output is correct

Subtask #2
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 128 KB Output is correct
2 Correct 5 ms 128 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 6 ms 384 KB Output is correct
5 Correct 15 ms 1148 KB Output is correct
6 Correct 203 ms 14432 KB Output is correct
7 Correct 199 ms 14344 KB Output is correct
8 Correct 205 ms 14428 KB Output is correct
9 Correct 5 ms 384 KB Output is correct
10 Correct 6 ms 384 KB Output is correct
11 Correct 6 ms 384 KB Output is correct
12 Correct 16 ms 1276 KB Output is correct
13 Correct 112 ms 7396 KB Output is correct
14 Correct 225 ms 14176 KB Output is correct
15 Correct 216 ms 14304 KB Output is correct
16 Correct 217 ms 14432 KB Output is correct

Subtask #3
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 128 KB Output is correct
2 Correct 5 ms 128 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 6 ms 384 KB Output is correct
5 Correct 15 ms 1148 KB Output is correct
6 Correct 203 ms 14432 KB Output is correct
7 Correct 199 ms 14344 KB Output is correct
8 Correct 205 ms 14428 KB Output is correct
9 Correct 5 ms 384 KB Output is correct
10 Correct 6 ms 384 KB Output is correct
11 Correct 6 ms 384 KB Output is correct
12 Correct 16 ms 1276 KB Output is correct
13 Correct 112 ms 7396 KB Output is correct
14 Correct 225 ms 14176 KB Output is correct
15 Correct 216 ms 14304 KB Output is correct
16 Correct 217 ms 14432 KB Output is correct
17 Correct 6 ms 384 KB Output is correct
18 Correct 6 ms 384 KB Output is correct
19 Correct 16 ms 1276 KB Output is correct
20 Correct 115 ms 7528 KB Output is correct
21 Correct 179 ms 12772 KB Output is correct
22 Correct 216 ms 14352 KB Output is correct
23 Correct 256 ms 14424 KB Output is correct
24 Correct 211 ms 14440 KB Output is correct
25 Correct 201 ms 14304 KB Output is correct
26 Correct 195 ms 14432 KB Output is correct