oj.uz

Submission #162254

# Submission time Handle Problem Language Result Execution time Memory
162254 2019-11-07T10:33:01 Z mosiashvililuka Divide and conquer (IZhO14_divide) C++14
100 / 100
 202 ms 21196 KB 
#include<bits/stdc++.h>
using namespace std;
long long a,b,c,d,e,zx,xc,fen[200009],jmz[100009],jmx[100009],pas;
pair <pair <long long, long long>, long long> p[100009];
map <long long, long long> m;
map <long long, long long>::iterator it;
long long read(long long q){
	if(q<=0) return 0;
	long long mn=fen[q];
	while(q>0){
		if(mn>fen[q]) mn=fen[q];
		q=q-(q&(-q));
	}
	return mn;
}
void upd(long long q, long long w){
	while(q<=200002){
		if(fen[q]>w) fen[q]=w;
		q=q+(q&(-q));
	}
}
int main(){
	ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>a;
	for(b=1; b<=a; b++){
		cin>>p[b].first.first>>p[b].first.second>>p[b].second;
		swap(p[b].first.second,p[b].second);
		if(pas<p[b].second) pas=p[b].second;
		jmz[b]=p[b].first.second+jmz[b-1];
		jmx[b]=jmx[b-1]+p[b].second;
		p[b].first.first++;
		m[jmz[b-1]-p[b].first.first]=1;
		m[jmz[b]-p[b].first.first]=1;
	}
	c=0;
	for(it=m.begin(); it!=m.end(); it++){
		c++;
		m[(*it).first]=c;
	}
	for(b=0; b<=200005; b++) fen[b]=999999999999999999LL;
	for(b=1; b<=a; b++){
		c=read(m[jmz[b]-p[b].first.first]);
		if(pas<jmx[b]-c) pas=jmx[b]-c;
		upd(m[jmz[b-1]-p[b].first.first],jmx[b-1]);
	}
	cout<<pas;
	return 0;
}

Subtask #1
17.0 / 17.0

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

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1960 KB Output is correct
2 Correct 4 ms 1960 KB Output is correct
3 Correct 4 ms 2040 KB Output is correct
4 Correct 4 ms 2012 KB Output is correct
5 Correct 4 ms 2040 KB Output is correct
6 Correct 5 ms 2168 KB Output is correct
7 Correct 4 ms 2040 KB Output is correct
8 Correct 5 ms 2040 KB Output is correct
9 Correct 5 ms 2168 KB Output is correct
10 Correct 6 ms 2296 KB Output is correct
11 Correct 10 ms 2808 KB Output is correct
12 Correct 10 ms 2808 KB Output is correct

Subtask #3
52.0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 2808 KB Output is correct
2 Correct 14 ms 3704 KB Output is correct
3 Correct 15 ms 3832 KB Output is correct
4 Correct 65 ms 11128 KB Output is correct
5 Correct 69 ms 11548 KB Output is correct
6 Correct 202 ms 21196 KB Output is correct
7 Correct 181 ms 20344 KB Output is correct
8 Correct 188 ms 20348 KB Output is correct
9 Correct 127 ms 20088 KB Output is correct
10 Correct 150 ms 19576 KB Output is correct
11 Correct 178 ms 20472 KB Output is correct
12 Correct 132 ms 20760 KB Output is correct