oj.uz

Submission #673690

# Submission time Handle Problem Language Result Execution time Memory
673690 2022-12-21T17:02:16 Z LastRonin Fire (JOI20_ho_t5) C++14
14 / 100
 1000 ms 54040 KB 
//#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math,O3")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define f first
#define s second
#define mp make_pair
#define speed ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)
using namespace std;

const int N = 2e5 + 100;


int n, q;
ll a[N];
int p[N], r[N];


ll st[6 * N], si[6 * N], sd[6 * N], que[6 * N];

ll ans[6 * N];


bool comp1(int i, int j) {
	if(st[i] == st[j])
		return (i < j);
	return (st[i] < st[j]);
}
bool comp2(int i, int j) {
	if(si[i] == si[j])
		return (i < j);
	return (si[i] < si[j]);
}

int shift;

struct seg {
	ll t[4 * N] = {0}, t2[4 * N] = {0};
	void clear(ll v = 1, ll tl = 0, ll tr = n + 4) {
		if(tl == tr) {
			t[v] = 0;
			t2[v] = 0;
			return;
		}
		ll m = (tl + tr) >> 1ll;
		clear(v * 2, tl, m);
		clear(v * 2 + 1, m + 1, tr);
		t[v] = 0;
		t2[v] = 0;
	}
	void upd(ll p, ll z, ll z2, ll v = 1, ll tl = 0, ll tr = n + 4) {
		if(tl == tr) {
			t[v] += z;
			t2[v] += z2;
			return; 
		}
		ll m = (tl + tr) >> 1ll;
		if(p <= m)upd(p, z, z2, v * 2, tl, m);
		else upd(p, z, z2, v * 2 + 1, m + 1, tr);
		t[v] = t[v * 2] + t[v * 2 + 1];
		t2[v] = t2[v * 2] + t2[v * 2 + 1];
	}
	pair<ll, ll> get(ll l, ll r, ll v = 1, ll tl = 0, ll tr = n + 4) {
		if(l > tr || tl > r) return mp(0, 0);
		if (l <= tl && tr <= r) return mp(t[v], t2[v]);
		ll m = (tl + tr) >> 1ll;
		pair<ll, ll> a = get(l, r, v * 2, tl, m);
		pair<ll, ll> b =  get(l, r, v * 2 + 1, m + 1, tr);
		return mp(a.f + b.f, a.s + b.s);
	}
} rt;


int main() {
	speed;
	cin >> n >> q;
	shift = n + 1;
	deque<int> s;
	for(int i = 1; i <= n; i++)
		cin >> a[i];
	for(int j = 1; j <= n; j++) {
		while(s.size() && a[s.back()] < a[j])s.pop_back();
		if(s.size())p[j] = s.back();
		s.push_back(j);
	}
	while(s.size())s.pop_back();
	
	for(int j = n; j >= 1; j--) {
		r[j] = n + 1;
		while(s.size() && a[s.back()] <= a[j])s.pop_back();
		if(s.size())r[j] = s.back();
		s.push_back(j);
	}
	int cnt = 1;
	for(int i = 1, t; i <= n; i++) {
		// 1
		st[cnt] = 1;
		sd[cnt] = a[i];
		si[cnt++] = i;
		// 2
		if(r[i] != n + 1) {
			st[cnt] = 1 + (r[i] - i);
			sd[cnt] = -a[i];
			si[cnt++] = r[i];
		}
		// 3
		if(p[i] != 0) {
			st[cnt] = 1 + (i - p[i]);
			sd[cnt] = -a[i];
			si[cnt++] = i;
			//4
			if(r[i] != n + 1) {
				st[cnt] = 1 + (r[i] - p[i]);  
				sd[cnt] = a[i];
				si[cnt++] = r[i];
			}
		}
	}
	vector<int> sbt;
	for(int i = 1; i <= n; i++)
		a[i] += a[i - 1];

	for(int i = 1; i <= q; i++) {
		ll t, l, r;
		cin >> t >> l >> r;
		t++;
		que[cnt] = i;
		st[cnt] = t;
		si[cnt++] = r;

		que[cnt] = -i;
		st[cnt] = t;
		si[cnt++] = l - 1;
	}
	//kek
	cnt--;
	for(int i = 1; i <= cnt; i++) {
		sbt.pb(i);
	}
	vector<int> queries;
	sort(sbt.begin(), sbt.end(), comp1);
	for(int i = 0; i < cnt; i++) {
		int s = sbt[i];
		if(que[s]) {
			ll qt = st[s], qi = si[s], znak = (que[s] < 0 ? -1 : 1);
			pair<ll, ll> ggg = rt.get(qt - qi + 1 + shift, n + 4);
			ans[que[s] * znak] += znak * (qt + 1) * ggg.f;
			ans[que[s] * znak] -= znak * ggg.s;
		} else {
			rt.upd(st[s] - si[s] + shift, sd[s], st[s] * sd[s]);
		}
	}
	rt.clear();
	sort(sbt.begin(), sbt.end(), comp2);
	for(int i = 0; i < cnt; i++) {
		int s = sbt[i];
		if(que[s]) {
			ll qt = st[s], qi = si[s], znak = (que[s] < 0 ? -1 : 1);
			pair<ll, ll> ggg = rt.get(0, qt - qi + shift);
			ans[que[s] * znak] += znak * (qi + 1) * ggg.f;
			ans[que[s] * znak] -= znak * ggg.s;
		} else {
			rt.upd(st[s] - si[s] + shift, sd[s], si[s] * sd[s]);
		}
	}
	for(int i = 1; i <= q; i++)
		cout << ans[i] << "\n";    
}

Compilation message

ho_t5.cpp: In function 'int main()':
ho_t5.cpp:96:17: warning: unused variable 't' [-Wunused-variable]
   96 |  for(int i = 1, t; i <= n; i++) {
      |                 ^

Subtask #1
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 324 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 2 ms 456 KB Output is correct
4 Correct 1 ms 452 KB Output is correct
5 Correct 2 ms 340 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 452 KB Output is correct
13 Correct 1 ms 460 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 468 KB Output is correct
16 Correct 1 ms 456 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 2 ms 340 KB Output is correct
19 Correct 1 ms 468 KB Output is correct
20 Correct 1 ms 468 KB Output is correct
21 Correct 1 ms 468 KB Output is correct
22 Correct 1 ms 340 KB Output is correct
23 Correct 1 ms 460 KB Output is correct
24 Correct 1 ms 456 KB Output is correct
25 Correct 1 ms 340 KB Output is correct
26 Correct 1 ms 456 KB Output is correct
27 Correct 1 ms 340 KB Output is correct
28 Correct 1 ms 456 KB Output is correct
29 Correct 1 ms 340 KB Output is correct
30 Correct 1 ms 340 KB Output is correct
31 Correct 1 ms 340 KB Output is correct
32 Correct 1 ms 456 KB Output is correct

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 324 KB Output is correct
2 Correct 671 ms 53780 KB Output is correct
3 Correct 678 ms 53628 KB Output is correct
4 Execution timed out 1026 ms 54040 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 324 KB Output is correct
2 Correct 731 ms 53080 KB Output is correct
3 Correct 807 ms 52256 KB Output is correct
4 Correct 781 ms 53700 KB Output is correct
5 Correct 756 ms 52428 KB Output is correct
6 Correct 748 ms 52824 KB Output is correct
7 Correct 774 ms 53024 KB Output is correct
8 Correct 809 ms 52976 KB Output is correct
9 Correct 880 ms 52500 KB Output is correct
10 Correct 752 ms 51992 KB Output is correct
11 Correct 846 ms 53584 KB Output is correct
12 Correct 918 ms 52928 KB Output is correct
13 Correct 854 ms 53444 KB Output is correct
14 Correct 802 ms 52540 KB Output is correct
15 Correct 862 ms 53328 KB Output is correct
16 Correct 854 ms 52736 KB Output is correct

Subtask #4
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 674 ms 45144 KB Output is correct
2 Correct 676 ms 45200 KB Output is correct
3 Correct 780 ms 46076 KB Output is correct
4 Correct 666 ms 45492 KB Output is correct
5 Correct 719 ms 45480 KB Output is correct
6 Correct 855 ms 45272 KB Output is correct
7 Correct 920 ms 45900 KB Output is correct
8 Correct 715 ms 45704 KB Output is correct
9 Correct 708 ms 45456 KB Output is correct
10 Correct 693 ms 45492 KB Output is correct
11 Correct 696 ms 45736 KB Output is correct
12 Correct 691 ms 45728 KB Output is correct
13 Correct 698 ms 45544 KB Output is correct
14 Correct 715 ms 45692 KB Output is correct

Subtask #5
0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 324 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 2 ms 456 KB Output is correct
4 Correct 1 ms 452 KB Output is correct
5 Correct 2 ms 340 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 452 KB Output is correct
13 Correct 1 ms 460 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 468 KB Output is correct
16 Correct 1 ms 456 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 2 ms 340 KB Output is correct
19 Correct 1 ms 468 KB Output is correct
20 Correct 1 ms 468 KB Output is correct
21 Correct 1 ms 468 KB Output is correct
22 Correct 1 ms 340 KB Output is correct
23 Correct 1 ms 460 KB Output is correct
24 Correct 1 ms 456 KB Output is correct
25 Correct 1 ms 340 KB Output is correct
26 Correct 1 ms 456 KB Output is correct
27 Correct 1 ms 340 KB Output is correct
28 Correct 1 ms 456 KB Output is correct
29 Correct 1 ms 340 KB Output is correct
30 Correct 1 ms 340 KB Output is correct
31 Correct 1 ms 340 KB Output is correct
32 Correct 1 ms 456 KB Output is correct
33 Correct 671 ms 53780 KB Output is correct
34 Correct 678 ms 53628 KB Output is correct
35 Execution timed out 1026 ms 54040 KB Time limit exceeded
36 Halted 0 ms 0 KB -