oj.uz

Submission #673696

# Submission time Handle Problem Language Result Execution time Memory
673696 2022-12-21T17:42:48 Z LastRonin Fire (JOI20_ho_t5) C++17
6 / 100
 505 ms 43316 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 fen {
	ll t[4 * N] = {0}, t2[4 * N] = {0};
	ll sum1 = 0, sum2 = 0;
	void clear() {
		sum1 = 0, sum2 = 0;
		for(int i = 0; i <= 2 * n; i++)
			t[i] = t2[i] = 0;
	}
	void add(ll p, ll z, ll z2) {
		sum1 += z, sum2 += z2;
		for(int i = p; i <= 2 * n; i = i|(i + 1)) {
			t[i] += z;
			t2[i] += z2;			
		}
	}
	pair<ll, ll> get(ll r) {
		ll s1 = 0, s2 = 0;
		for(int i = r; i >= 0; i = (i&(i+1)) - 1) {
			s1 += t[i];
			s2 += t2[i];  
		}
		return mp(s1, s2);
	}
} ret;
 
 
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 = ret.get(qt - qi + shift);
			ggg.f = ret.sum1 - ggg.f;
			ggg.s = ret.sum2 - ggg.s;
			ans[que[s] * znak] += znak * (qt + 1) * ggg.f;
			ans[que[s] * znak] -= znak * ggg.s;
		} else {
			ret.add(st[s] - si[s] + shift, sd[s], st[s] * sd[s]);
		}
	}
	ret.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 = ret.get(qt - qi + shift);
			ans[que[s] * znak] += znak * (qi + 1) * ggg.f;
			ans[que[s] * znak] -= znak * ggg.s;
		} else {
			ret.add(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:85:17: warning: unused variable 't' [-Wunused-variable]
   85 |  for(int i = 1, t; i <= n; i++) {
      |                 ^

Subtask #1
0 / 1.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 479 ms 39192 KB Output is correct
2 Correct 451 ms 42296 KB Output is correct
3 Correct 505 ms 43316 KB Output is correct
4 Correct 486 ms 42312 KB Output is correct
5 Correct 464 ms 42460 KB Output is correct
6 Correct 464 ms 42292 KB Output is correct
7 Correct 484 ms 42936 KB Output is correct
8 Correct 477 ms 42800 KB Output is correct
9 Correct 499 ms 42436 KB Output is correct
10 Correct 465 ms 42488 KB Output is correct
11 Correct 480 ms 42492 KB Output is correct
12 Correct 470 ms 42540 KB Output is correct
13 Correct 472 ms 42448 KB Output is correct
14 Correct 478 ms 42524 KB Output is correct

Subtask #5
0 / 80.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -