oj.uz

Submission #916055

# Submission time Handle Problem Language Result Execution time Memory
916055 2024-01-25T08:14:40 Z GrindMachine Gap (APIO16_gap) C++17
0 / 100
 2000 ms 15260 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

template<typename T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
typedef long long int ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL)
#define pb push_back
#define endl '\n'
#define sz(a) (int)a.size()
#define setbits(x) __builtin_popcountll(x)
#define ff first
#define ss second
#define conts continue
#define ceil2(x,y) ((x+y-1)/(y))
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define yes cout << "Yes" << endl
#define no cout << "No" << endl

#define rep(i,n) for(int i = 0; i < n; ++i)
#define rep1(i,n) for(int i = 1; i <= n; ++i)
#define rev(i,s,e) for(int i = s; i >= e; --i)
#define trav(i,a) for(auto &i : a)

template<typename T>
void amin(T &a, T b) {
    a = min(a,b);
}

template<typename T>
void amax(T &a, T b) {
    a = max(a,b);
}

#ifdef LOCAL
#include "debug.h"
#else
#define debug(x) 42
#endif

/*

read some solutions a long time ago, slightly remember some ideas
may have still solved it if not for those ideas

*/

const int MOD = 1e9 + 7;
const int N = 1e5 + 5;
const int inf1 = int(1e9) + 5;
const ll inf2 = ll(1e18) + 5;
const int B = 1e5 + 5;

#include "gap.h"

ll go(ll l, ll r){
	if(l >= r) return 0;

	// split into B segs
	ll len = r-l+1;
	ll cnt1 = B;
	ll cnt2 = len%B;
	cnt1 -= cnt2;

	vector<pll> segs;
	ll ptr = l;

	rep1(i,cnt1){
		if(len >= B){
			segs.pb({ptr,ptr+len/B-1});
		}
		ptr += len/B;
	}

	rep1(i,cnt2){
		segs.pb({ptr,ptr+ceil2(len,B)-1});
		ptr += ceil2(len,B);
	}

	// cout << "l = " << l << endl;
	// cout << "r = " << r << endl;
	// for(auto [lx,rx] : segs){
	// 	cout << lx << " " << rx << endl;
	// }

	assert(ptr == r+1);

	vector<pll> seg_vals;
	ll ans = 0;

	rep(i,sz(segs)){
		ll mn,mx;
		auto [lx,rx] = segs[i];
		MinMax(lx,rx,&mn,&mx);
		seg_vals.pb({mn,mx});
		if(mn != -1){
			amax(ans,go(lx,rx));
		}
	}

	ll last_active = -1;

	for(auto [mn,mx] : seg_vals){
		if(mn != -1){
			if(last_active != -1){
				amax(ans,mn-last_active);
			}
			last_active = mx;
		}
	}

	return ans;
}

long long findGap(int T, int n)
{
	return go(0,inf2);
}

Subtask #1
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 21 ms 11220 KB Output isn't correct
2 Incorrect 147 ms 13764 KB Output isn't correct
3 Incorrect 147 ms 13216 KB Output isn't correct
4 Incorrect 149 ms 13856 KB Output isn't correct
5 Incorrect 23 ms 10448 KB Output isn't correct
6 Incorrect 1287 ms 13596 KB Output isn't correct
7 Incorrect 1316 ms 13508 KB Output isn't correct
8 Incorrect 1386 ms 14000 KB Output isn't correct
9 Incorrect 1289 ms 15200 KB Output isn't correct
10 Incorrect 24 ms 10192 KB Output isn't correct
11 Execution timed out 3034 ms 12880 KB Time limit exceeded
12 Execution timed out 3045 ms 14796 KB Time limit exceeded
13 Execution timed out 3012 ms 12700 KB Time limit exceeded
14 Execution timed out 3016 ms 13080 KB Time limit exceeded
15 Incorrect 507 ms 11820 KB Output isn't correct
16 Execution timed out 3040 ms 12844 KB Time limit exceeded
17 Execution timed out 3046 ms 12520 KB Time limit exceeded
18 Execution timed out 3024 ms 12472 KB Time limit exceeded
19 Execution timed out 3056 ms 12664 KB Time limit exceeded
20 Incorrect 51 ms 10368 KB Output isn't correct
21 Execution timed out 3066 ms 12808 KB Time limit exceeded
22 Execution timed out 3060 ms 12916 KB Time limit exceeded
23 Execution timed out 3047 ms 12784 KB Time limit exceeded
24 Execution timed out 3019 ms 12916 KB Time limit exceeded
25 Execution timed out 3019 ms 12372 KB Time limit exceeded
26 Execution timed out 3048 ms 12900 KB Time limit exceeded
27 Execution timed out 3006 ms 13508 KB Time limit exceeded
28 Execution timed out 3037 ms 12720 KB Time limit exceeded
29 Execution timed out 3030 ms 12972 KB Time limit exceeded
30 Incorrect 92 ms 10632 KB Output isn't correct
31 Incorrect 354 ms 13952 KB Output isn't correct
32 Incorrect 351 ms 13960 KB Output isn't correct

Subtask #2
0 / 70.0

# Verdict Execution time Memory Grader output
1 Partially correct 20 ms 12844 KB Partially correct
2 Partially correct 147 ms 13224 KB Partially correct
3 Partially correct 142 ms 13628 KB Partially correct
4 Partially correct 152 ms 13308 KB Partially correct
5 Partially correct 19 ms 10192 KB Partially correct
6 Partially correct 1308 ms 14444 KB Partially correct
7 Partially correct 1357 ms 14752 KB Partially correct
8 Partially correct 1285 ms 13732 KB Partially correct
9 Partially correct 1331 ms 15260 KB Partially correct
10 Partially correct 23 ms 10192 KB Partially correct
11 Execution timed out 3018 ms 15032 KB Time limit exceeded
12 Execution timed out 3096 ms 13532 KB Time limit exceeded
13 Execution timed out 3009 ms 14968 KB Time limit exceeded
14 Execution timed out 3025 ms 12632 KB Time limit exceeded
15 Partially correct 490 ms 11852 KB Partially correct
16 Execution timed out 3041 ms 12420 KB Time limit exceeded
17 Execution timed out 3011 ms 12644 KB Time limit exceeded
18 Execution timed out 3047 ms 12616 KB Time limit exceeded
19 Execution timed out 3042 ms 12548 KB Time limit exceeded
20 Partially correct 58 ms 10236 KB Partially correct
21 Execution timed out 3065 ms 12704 KB Time limit exceeded
22 Execution timed out 3054 ms 12608 KB Time limit exceeded
23 Execution timed out 3041 ms 13164 KB Time limit exceeded
24 Execution timed out 3014 ms 12732 KB Time limit exceeded
25 Execution timed out 3014 ms 12056 KB Time limit exceeded
26 Execution timed out 3090 ms 12864 KB Time limit exceeded
27 Execution timed out 3029 ms 12956 KB Time limit exceeded
28 Execution timed out 3024 ms 13000 KB Time limit exceeded
29 Execution timed out 3036 ms 13672 KB Time limit exceeded
30 Partially correct 88 ms 10636 KB Partially correct
31 Partially correct 363 ms 13912 KB Partially correct
32 Partially correct 347 ms 14160 KB Partially correct