oj.uz

답안 #200784

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
200784 2020-02-08T06:49:45 Z dimash241 Gap (APIO16_gap) C++17
100 / 100
 79 ms 1304 KB 
#include "gap.h"
 
# include <bits/stdc++.h>
 
# include <ext/pb_ds/assoc_container.hpp>
# include <ext/pb_ds/tree_policy.hpp>
 
using namespace __gnu_pbds;
using namespace std;
 
template<typename T> using ordered_set = tree <T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
 
#define _USE_MATH_DEFINES_
#define ll long long
#define ld long double
#define Accepted 0
#define pb push_back
#define mp make_pair
#define sz(x) (int)(x.size())
#define every(x) x.begin(),x.end()
#define F first
#define S second
#define lb lower_bound
#define ub upper_bound
#define For(i,x,y)  for (ll i = x; i <= y; i ++) 
#define FOr(i,x,y)  for (ll i = x; i >= y; i --)
#define SpeedForce ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)
// ROAD to...                                                                                                                                                                                                                Red
 
inline void Input_Output () {
	//freopen(".in", "r", stdin);
   //freopen(".out", "w", stdout);
}
 
const double eps = 0.000001;
const ld pi = acos(-1);
const int maxn = 1e7 + 9;
const int mod = 1e9 + 7;
const ll MOD = 1e18 + 9;
const ll INF = 1e18 + 123;
const int inf = 2e9 + 11;
const int mxn = 1e6 + 9;
const int N = 6e5 + 123;                                          
const int M = 22;
const int pri = 997;
const int Magic = 2101;
 
const int dx[] = {-1, 0, 1, 0};
const int dy[] = {0, -1, 0, 1};
 
 
ll solve1 (int n) {
	ll l, r, res = 0;
    MinMax(0, INF, &l, &r);
    int cnt = 2; 
 
    while (cnt < n) {
        ll m1, m2;
        MinMax(l + 1, r - 1, &m1, &m2);
        res = max(res, m1 - l);
        res = max(res, r - m2);
        l = m1;
        r = m2;
        cnt += 2;
    }
 
    res = max(res, r - l);
    return res;
}
ll L[N], R[N];
 
ll solve2 (int n) {
	ll l, r, res = 0;
    MinMax(0, INF, &l, &r);
    R[n] = r;
    L[1] = l;
    ll lim = (r - l + n - 1) / n, lst = l;
 
    for (int i = 1; i <= n; i ++) {
    	ll s = l + 1;
    	ll t = min(r, l + lim);
    	if (s > t) break;
    	ll cl, cr;
    	MinMax(s, t, &cl, &cr);
    	if (cl != -1) {
    		res = max(res, cl - lst);
    		lst = cr;
    	}
    	l += lim;
    }
    res = max(res, r - lst);
    return res;
}
 
long long findGap(int T, int N) {	
	if (T == 1) return solve1(N);
	return solve2(N);
}

Subtask #1
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 248 KB Output is correct
2 Correct 5 ms 248 KB Output is correct
3 Correct 5 ms 248 KB Output is correct
4 Correct 5 ms 376 KB Output is correct
5 Correct 5 ms 248 KB Output is correct
6 Correct 5 ms 376 KB Output is correct
7 Correct 5 ms 248 KB Output is correct
8 Correct 4 ms 248 KB Output is correct
9 Correct 5 ms 376 KB Output is correct
10 Correct 5 ms 248 KB Output is correct
11 Correct 5 ms 252 KB Output is correct
12 Correct 5 ms 248 KB Output is correct
13 Correct 5 ms 248 KB Output is correct
14 Correct 6 ms 248 KB Output is correct
15 Correct 5 ms 248 KB Output is correct
16 Correct 16 ms 504 KB Output is correct
17 Correct 20 ms 504 KB Output is correct
18 Correct 23 ms 504 KB Output is correct
19 Correct 20 ms 504 KB Output is correct
20 Correct 13 ms 504 KB Output is correct
21 Correct 56 ms 1144 KB Output is correct
22 Correct 63 ms 1144 KB Output is correct
23 Correct 55 ms 1016 KB Output is correct
24 Correct 64 ms 1144 KB Output is correct
25 Correct 47 ms 1112 KB Output is correct
26 Correct 54 ms 1016 KB Output is correct
27 Correct 55 ms 1016 KB Output is correct
28 Correct 54 ms 1116 KB Output is correct
29 Correct 64 ms 1016 KB Output is correct
30 Correct 40 ms 1304 KB Output is correct
31 Correct 5 ms 248 KB Output is correct
32 Correct 5 ms 380 KB Output is correct

Subtask #2
70.0 / 70.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 248 KB Output is correct
2 Correct 4 ms 248 KB Output is correct
3 Correct 5 ms 252 KB Output is correct
4 Correct 5 ms 508 KB Output is correct
5 Correct 5 ms 248 KB Output is correct
6 Correct 5 ms 376 KB Output is correct
7 Correct 5 ms 376 KB Output is correct
8 Correct 5 ms 248 KB Output is correct
9 Correct 5 ms 248 KB Output is correct
10 Correct 5 ms 248 KB Output is correct
11 Correct 5 ms 376 KB Output is correct
12 Correct 6 ms 536 KB Output is correct
13 Correct 5 ms 376 KB Output is correct
14 Correct 5 ms 248 KB Output is correct
15 Correct 5 ms 248 KB Output is correct
16 Correct 23 ms 440 KB Output is correct
17 Correct 21 ms 504 KB Output is correct
18 Correct 21 ms 504 KB Output is correct
19 Correct 21 ms 504 KB Output is correct
20 Correct 13 ms 504 KB Output is correct
21 Correct 79 ms 1068 KB Output is correct
22 Correct 74 ms 1216 KB Output is correct
23 Correct 77 ms 1300 KB Output is correct
24 Correct 73 ms 1016 KB Output is correct
25 Correct 64 ms 1076 KB Output is correct
26 Correct 77 ms 1276 KB Output is correct
27 Correct 73 ms 1144 KB Output is correct
28 Correct 74 ms 1016 KB Output is correct
29 Correct 72 ms 1144 KB Output is correct
30 Correct 40 ms 1136 KB Output is correct
31 Correct 4 ms 248 KB Output is correct
32 Correct 5 ms 248 KB Output is correct