oj.uz

Submission #894698

# Submission time Handle Problem Language Result Execution time Memory
894698 2023-12-28T17:55:04 Z vjudge1 Divide and conquer (IZhO14_divide) C++17
100 / 100
 57 ms 16260 KB 
#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
  
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
 
 #pragma GCC optimize("Ofast,unroll-loops,fast-math")
 #pragma GCC target("popcnt")


typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<ll,ll> pll;
 
#define sz size()
#define ff first
#define ss second
#define all(a) a.begin(),a.end()
#define pb push_back

const int mod = ll(1e9)+7; //(b + (a%b)) % b (to mod -1%(10^9+7) correctly in c++ its -1 but its suppose to be 10^9+6
const ll MOD = 998244353;  // (a%mod)*(binpow(b,mod-2,mod) = (a/b)%mod
const int N = ll(3e5)+100;
const int M = ll(2e5) + 100;
const long long inf = 2e18;
const long double eps = 1e-15L;
 
ll lcm(ll a, ll b) { return (a / __gcd(a,b))*b; }

ll binpow(ll a, ll b, ll m) { ll res=1; a %= m; while(b>0){ if(b&1)res=(res * a) % m; a=(a * a) % m; b/=2; } return res%m;}

void Freopen(string Key){ freopen((Key+".in").c_str(), "r", stdin); freopen((Key+".out").c_str(), "w", stdout); }

int n, x[N], g[N], d[N], t[N*4];
ll pr[N], prg[N];

void build(int v, int tl, int tr) {
	if(tl == tr) {
		t[v] = 1e9;
		return;
	}
	int tm = (tl + tr) / 2;
	build(v + v, tl, tm);
	build(v + v + 1, tm + 1, tr);
	t[v] = min(t[v + v], t[v + v + 1]);
}

void update(int v, int tl, int tr, int p, int x) {
	if(tl == tr) {
		t[v] = min(t[v], x);
		return;
	}
	int tm = (tl + tr) / 2;
	if(p <= tm) update(v + v, tl, tm, p, x);
	else update(v + v + 1, tm + 1, tr, p, x);
	t[v] = min(t[v + v], t[v + v + 1]);
}

int get(int v, int tl, int tr, int l, int r) {
	if(tl > r || l > tr) return 1e9;
	if(l <= tl && tr <= r) return t[v];
	int tm = (tl + tr) / 2;
	return min(get(v + v, tl, tm, l, r), get(v + v + 1, tm + 1, tr, l, r));
}

vector<ll> comp;

int id(ll x) {
	return upper_bound(all(comp), x) - comp.begin();
}

void Baizho() {
	cin>>n;
	for(int i = 1; i <= n; i ++) {
		cin>>x[i]>>g[i]>>d[i];
		prg[i] = prg[i - 1] + g[i];
		pr[i] = pr[i - 1] + d[i];
		comp.pb(x[i] - pr[i]);
		comp.pb(x[i] - pr[i - 1]);
	}
	sort(all(comp));
	comp.erase(unique(all(comp)), comp.end());
	build(1, 1, comp.sz);
	ll ans = 0;
	for(int i = 1; i <= n; i ++) {
//		cout<<x[i] - pr[i - 1]<<" "<<x[i] - pr[i]<<"\n";
		update(1, 1, comp.sz, id(x[i] - pr[i - 1]), i);
		int j = get(1, 1, comp.sz, id(x[i] - pr[i]), comp.sz);
		ans = max(ans, prg[i] - prg[j - 1]);
	}
	cout<<ans<<"\n";
	
}
 
signed main() {		
// 	Freopen("nondec");
    ios_base::sync_with_stdio(false);   
    cin.tie(0);cout.tie(0); 
//   	precalc();
   	
    int ttt = 1;
//    cin>>ttt;

    for(int i=1; i<=ttt; i++) {Baizho(); }
}

Compilation message

divide.cpp: In function 'void Freopen(std::string)':
divide.cpp:35:34: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   35 | void Freopen(string Key){ freopen((Key+".in").c_str(), "r", stdin); freopen((Key+".out").c_str(), "w", stdout); }
      |                           ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
divide.cpp:35:76: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   35 | void Freopen(string Key){ freopen((Key+".in").c_str(), "r", stdin); freopen((Key+".out").c_str(), "w", stdout); }
      |                                                                     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 1 ms 6616 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 1 ms 6604 KB Output is correct
5 Correct 1 ms 6492 KB Output is correct
6 Correct 1 ms 6492 KB Output is correct
7 Correct 1 ms 6492 KB Output is correct
8 Correct 1 ms 6492 KB Output is correct
9 Correct 1 ms 6492 KB Output is correct
10 Correct 1 ms 6492 KB Output is correct
11 Correct 1 ms 6492 KB Output is correct
12 Correct 1 ms 6492 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 1 ms 6616 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 1 ms 6604 KB Output is correct
5 Correct 1 ms 6492 KB Output is correct
6 Correct 1 ms 6492 KB Output is correct
7 Correct 1 ms 6492 KB Output is correct
8 Correct 1 ms 6492 KB Output is correct
9 Correct 1 ms 6492 KB Output is correct
10 Correct 1 ms 6492 KB Output is correct
11 Correct 1 ms 6492 KB Output is correct
12 Correct 1 ms 6492 KB Output is correct
13 Correct 1 ms 6488 KB Output is correct
14 Correct 1 ms 6492 KB Output is correct
15 Correct 1 ms 6612 KB Output is correct
16 Correct 1 ms 6492 KB Output is correct
17 Correct 2 ms 6488 KB Output is correct
18 Correct 2 ms 6492 KB Output is correct
19 Correct 1 ms 6492 KB Output is correct
20 Correct 1 ms 6492 KB Output is correct
21 Correct 2 ms 6492 KB Output is correct
22 Correct 2 ms 6748 KB Output is correct
23 Correct 3 ms 7004 KB Output is correct
24 Correct 3 ms 7004 KB Output is correct

Subtask #3
52.0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 1 ms 6616 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 1 ms 6604 KB Output is correct
5 Correct 1 ms 6492 KB Output is correct
6 Correct 1 ms 6492 KB Output is correct
7 Correct 1 ms 6492 KB Output is correct
8 Correct 1 ms 6492 KB Output is correct
9 Correct 1 ms 6492 KB Output is correct
10 Correct 1 ms 6492 KB Output is correct
11 Correct 1 ms 6492 KB Output is correct
12 Correct 1 ms 6492 KB Output is correct
13 Correct 1 ms 6488 KB Output is correct
14 Correct 1 ms 6492 KB Output is correct
15 Correct 1 ms 6612 KB Output is correct
16 Correct 1 ms 6492 KB Output is correct
17 Correct 2 ms 6488 KB Output is correct
18 Correct 2 ms 6492 KB Output is correct
19 Correct 1 ms 6492 KB Output is correct
20 Correct 1 ms 6492 KB Output is correct
21 Correct 2 ms 6492 KB Output is correct
22 Correct 2 ms 6748 KB Output is correct
23 Correct 3 ms 7004 KB Output is correct
24 Correct 3 ms 7004 KB Output is correct
25 Correct 3 ms 6748 KB Output is correct
26 Correct 6 ms 7136 KB Output is correct
27 Correct 6 ms 7136 KB Output is correct
28 Correct 25 ms 10968 KB Output is correct
29 Correct 26 ms 11220 KB Output is correct
30 Correct 53 ms 16260 KB Output is correct
31 Correct 47 ms 15048 KB Output is correct
32 Correct 48 ms 15048 KB Output is correct
33 Correct 47 ms 14804 KB Output is correct
34 Correct 57 ms 14748 KB Output is correct
35 Correct 49 ms 15304 KB Output is correct
36 Correct 50 ms 15560 KB Output is correct