oj.uz

Submission #150275

# Submission time Handle Problem Language Result Execution time Memory
150275 2019-09-01T08:02:24 Z 20190901(#3597, tongnamuu, jf297, upple1) Crosses on the Grid (FXCUP4_cross) C++17
8 / 100
 291 ms 17772 KB 
#include "cross.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
pair<int, int> arr[200005];
ll it[800005], ot[800005];
int n;
const ll INF=0x3f3f3f3f3f3f3f3fLL;
ll update(ll st[], int idx, ll v, int p, int x, int y)
{
    if(idx<x || idx>y) return st[p];
    if(x==y) return st[p]=v;
    int mid=x+y>>1;
    return st[p]=min(update(st, idx, v, p<<1, x, mid), update(st, idx, v, (p<<1)+1, mid+1, y));
}

long long SelectCross(int K, std::vector<int> I, std::vector<int> O)
{
    n=I.size();
	memset(it, 0x3f, sizeof(it));
	memset(ot, 0x3f, sizeof(ot));
    for(int i=0; i<n; i++)
    {
        arr[i]={O[i], I[i]};
    }

    sort(arr, arr+n);
    for(int i=0; i<K; i++)
    {
        update(ot, i, arr[i].first, 1, 0, n);
        update(it, i, arr[i].second, 1, 0, n);
    }

    ll ans=0;
    for(int i=0; i<n; i++)
    {
        ll isize=it[1], osize=ot[1];
        ans=max(ans, osize*osize-(osize-isize)*(osize-isize));
		// cout<<ans<<' ';
        update(ot, i, INF, 1, 0, n);
        update(it, i, INF, 1, 0, n);
        update(ot, (i+K)%n, arr[(i+K)%n].first, 1, 0, n);
        update(it, (i+K)%n, arr[(i+K)%n].second, 1, 0, n);
    }

	return ans;
}

Compilation message

cross.cpp: In function 'll update(ll*, int, ll, int, int, int)':
cross.cpp:13:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int mid=x+y>>1;
             ~^~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 12928 KB Output is correct
2 Correct 11 ms 12972 KB Output is correct
3 Correct 12 ms 12928 KB Output is correct
4 Correct 13 ms 12928 KB Output is correct
5 Correct 27 ms 13184 KB Output is correct
6 Correct 291 ms 17764 KB Output is correct
7 Correct 289 ms 17688 KB Output is correct
8 Correct 280 ms 17772 KB Output is correct

Subtask #2
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 12928 KB Output is correct
2 Correct 11 ms 12972 KB Output is correct
3 Correct 12 ms 12928 KB Output is correct
4 Correct 13 ms 12928 KB Output is correct
5 Correct 27 ms 13184 KB Output is correct
6 Correct 291 ms 17764 KB Output is correct
7 Correct 289 ms 17688 KB Output is correct
8 Correct 280 ms 17772 KB Output is correct
9 Correct 12 ms 12928 KB Output is correct
10 Incorrect 12 ms 12928 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #3
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 12928 KB Output is correct
2 Correct 11 ms 12972 KB Output is correct
3 Correct 12 ms 12928 KB Output is correct
4 Correct 13 ms 12928 KB Output is correct
5 Correct 27 ms 13184 KB Output is correct
6 Correct 291 ms 17764 KB Output is correct
7 Correct 289 ms 17688 KB Output is correct
8 Correct 280 ms 17772 KB Output is correct
9 Correct 12 ms 12928 KB Output is correct
10 Incorrect 12 ms 12928 KB Output isn't correct
11 Halted 0 ms 0 KB -