oj.uz

Submission #366287

# Submission time Handle Problem Language Result Execution time Memory
366287 2021-02-13T19:28:17 Z model_code Janjetina (COCI21_janjetina) C++17
35 / 110
 439 ms 2288 KB 
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

typedef long long ll;
typedef pair <int, int> pii;
#define x first
#define y second
#define mp make_pair

const int MAXN = (int)1e5;
int n, k, a[MAXN + 5];
vector <pii> v;
ll f[MAXN + 5], sol;

void update(int x, ll y){
	x++;
	for(int i = x ; i <= MAXN + 2 ; i += (i & -i)){
		f[i] += y;
	}
}

ll query(int x){
	ll ret = 0;
	x++;
	for( ; x > 0 ; x -= (x & -x)){
		ret += f[x];
	}
	return ret;
}

void procesiraj_aktivne(ll pred){
	sort(v.begin(), v.end());
	for(int i = 0 ; i < (int)v.size() ; ++i){
		sol = sol + pred * query(v[i].x - v[i].y - k);
		update(v[i].y, 1);
	}
	for(int i = 0 ; i < (int)v.size() ; ++i){
		update(v[i].y, -1);
	}
	v.clear();
}

void rek(int l, int r){
	if(l >= r)
		return;
	int mid = (l + r) / 2;
	rek(l, mid);
	rek(mid + 1, r);
	int maxi = 0;
	for(int i = mid ; i >= l ; --i){
		v.push_back(mp(maxi, mid - i));
		maxi = max(maxi, a[i - 1]);
	}
	maxi = 0;
	for(int i = mid ; i < r ; ++i){
		maxi = max(maxi, a[i]);
		v.push_back(mp(maxi, i - mid + 1));
	}
	procesiraj_aktivne(1);
	maxi = 0;
	for(int i = mid ; i >= l ; --i){
		v.push_back(mp(maxi, mid - i));
		maxi = max(maxi, a[i - 1]);
	}
	procesiraj_aktivne(-1);
	maxi = 0;
	for(int i = mid ; i < r ; ++i){
		maxi = max(maxi, a[i]);
		v.push_back(mp(maxi, i - mid + 1));
	}
	procesiraj_aktivne(-1);
}

int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n >> k;
for(int i = 1 ; i < n ; ++i){
	int x, y, w;
	cin >> x >> y >> w;
	a[i] = w;
}
rek(1, n);
sol *= 2LL;
cout << sol << endl;

return 0;
}

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 0 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 3 ms 364 KB Output is correct
5 Correct 3 ms 364 KB Output is correct
6 Correct 3 ms 364 KB Output is correct
7 Correct 3 ms 364 KB Output is correct
8 Correct 3 ms 364 KB Output is correct
9 Correct 3 ms 364 KB Output is correct
10 Incorrect 3 ms 364 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #2
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 3 ms 364 KB Output is correct
5 Correct 28 ms 620 KB Output is correct
6 Correct 187 ms 1264 KB Output is correct
7 Correct 355 ms 2284 KB Output is correct
8 Correct 402 ms 2156 KB Output is correct
9 Correct 369 ms 2184 KB Output is correct
10 Correct 431 ms 2184 KB Output is correct
11 Correct 370 ms 2172 KB Output is correct
12 Correct 413 ms 2172 KB Output is correct
13 Correct 358 ms 2284 KB Output is correct
14 Correct 407 ms 2272 KB Output is correct
15 Correct 421 ms 2156 KB Output is correct
16 Correct 405 ms 2156 KB Output is correct
17 Correct 439 ms 2288 KB Output is correct
18 Correct 425 ms 2264 KB Output is correct

Subtask #3
0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 0 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 3 ms 364 KB Output is correct
5 Correct 3 ms 364 KB Output is correct
6 Correct 3 ms 364 KB Output is correct
7 Correct 3 ms 364 KB Output is correct
8 Correct 3 ms 364 KB Output is correct
9 Correct 3 ms 364 KB Output is correct
10 Incorrect 3 ms 364 KB Output isn't correct
11 Halted 0 ms 0 KB -