oj.uz

Submission #534412

# Submission time Handle Problem Language Result Execution time Memory
534412 2022-03-08T06:47:23 Z Haruto810198 Fire (JOI20_ho_t5) C++17
6 / 100
 228 ms 35524 KB 
#include <bits/stdc++.h>
 
using namespace std;
 
#define int long long
#define double long double
 
#define FOR(i, l, r, d) for(int i=(l); i<=(r); i+=(d))
#define szof(x) ((int)(x).size())
 
#define vi vector<int>
#define pii pair<int, int>
 
#define F first
#define S second
 
#define pb push_back
#define eb emplace_back
#define mkp make_pair

#define lsb(x) ((x)&(-(x)))

const int INF = INT_MAX;
const int LNF = INF*INF;
const int MOD = 1000000007;
const int mod = 998244353;
const double eps = 1e-12;
 
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("unroll-loops")

const int MAX = 200010;

int n, q;
int arr[MAX];
int l[MAX], r[MAX];

int cnt[MAX], sum[MAX];

struct Query{
	int l, r, t, id;
};
Query query[MAX];
int res[MAX];

vi ev[MAX];

void modify(int id, int val){
	
	int pos = id;

	//if(val == 1) cerr<<"+ ";
	//else cerr<<"- ";
	//cerr<<id<<endl;

	while(pos < n){
		cnt[pos] += val;
		sum[pos] += arr[id] * val;
		pos += lsb(pos);
	}
}

int search(int qcnt){
	int ret = 0;
	int ptr = 0;
	for(int j = 19; j >= 0; j--){
		int np = ptr + (1<<j);
		if(np >= n) continue;
		if(qcnt > cnt[np]){
			qcnt -= cnt[np];
			ret += sum[np];
			ptr = np;
		}
	}

	if(ptr + 1 < n){
		ret += qcnt * arr[ptr + 1];
	}
	return ret;
}

signed main(){
	
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
	
	cin>>n>>q;
	FOR(i, 1, n, 1){
		cin>>arr[i];
	}

	FOR(i, 1, q, 1){
		cin>>query[i].t>>query[i].l>>query[i].r;
		query[i].id = i;
	}
	sort(query+1, query+q+1, [&](Query a, Query b){
		return (a.t < b.t);
	});
	
	arr[0] = arr[n+1] = INF;
	
	// l
	vi stk;
	stk.pb(0);
	FOR(i, 1, n, 1){
		while(arr[stk.back()] < arr[i]) stk.pop_back();
		l[i] = stk.back();
		stk.pb(i);
	}

	stk.clear();
	stk.pb(n+1);
	for(int i=n; i>=1; i--){
		while(arr[stk.back()] <= arr[i]) stk.pop_back();
		r[i] = stk.back();
		stk.pb(i);
	}
	
	// + : [1, r[i] - i - 1]
	// - : [i - l[i], i - l[i] + (r[i] - i - 1)]
	
	FOR(i, 1, n, 1){
		int ilen = r[i] - i - 1, dt = i - l[i];
		
		if(l[i] == 0){
			FOR(j, 1, ilen, 1){
				if(j > n) break;
				ev[j].pb(i);
			}
		}
		else{
			if(ilen < dt){
				FOR(j, 1, ilen, 1){
					if(j > n) break;
					ev[j].pb(i);
				}
				FOR(j, dt, dt + ilen, 1){
					if(j > n) break;
					ev[j].pb(-i);
				}
			}
			else{
				FOR(j, 1, dt - 1, 1){
					if(j > n) break;
					ev[j].pb(i);
				}
				FOR(j, ilen + 1, dt + ilen, 1){
					if(j > n) break;
					ev[j].pb(-i);
				}
			}
		}
	}
	
	// t = 0
	FOR(i, 1, n, 1){
		modify(i, 1);
	}
	
	int ptr = 0;
	FOR(i, 1, q, 1){
		while(ptr < query[i].t){
			// ptr -> ptr+1
			ptr++;
			for(int e : ev[ptr]){
				if(e > 0) modify(e, 1);
				else modify(-e, -1);
			}
		}
		
		res[query[i].id] = search(query[i].r) - search(query[i].l - 1);
		//cerr<<"query ["<<query[i].l<<", "<<query[i].r<<"] "<<endl;
	}
	
	FOR(i, 1, q, 1){
		cout<<res[i]<<'\n';
	}

	return 0;
	
}

Subtask #1
0 / 1.0

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

Subtask #2
0 / 6.0

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

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 4940 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 205 ms 30508 KB Output is correct
2 Correct 197 ms 30780 KB Output is correct
3 Correct 219 ms 35524 KB Output is correct
4 Correct 193 ms 34608 KB Output is correct
5 Correct 191 ms 35252 KB Output is correct
6 Correct 193 ms 34332 KB Output is correct
7 Correct 201 ms 35284 KB Output is correct
8 Correct 224 ms 34760 KB Output is correct
9 Correct 208 ms 34980 KB Output is correct
10 Correct 201 ms 34480 KB Output is correct
11 Correct 201 ms 34968 KB Output is correct
12 Correct 228 ms 35140 KB Output is correct
13 Correct 191 ms 34716 KB Output is correct
14 Correct 206 ms 35228 KB Output is correct

Subtask #5
0 / 80.0

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