oj.uz

Submission #534416

# Submission time Handle Problem Language Result Execution time Memory
534416 2022-03-08T06:52:26 Z Haruto810198 Fire (JOI20_ho_t5) C++17
6 / 100
 222 ms 31568 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];
int owo;

void modify(int id, int val){
	
	owo += 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);
			}

			assert(owo == n);
		}
		
		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 4 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 4 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 4 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 210 ms 30604 KB Output is correct
2 Correct 197 ms 30808 KB Output is correct
3 Correct 203 ms 31568 KB Output is correct
4 Correct 192 ms 30772 KB Output is correct
5 Correct 222 ms 31176 KB Output is correct
6 Correct 180 ms 30528 KB Output is correct
7 Correct 185 ms 31348 KB Output is correct
8 Correct 220 ms 30852 KB Output is correct
9 Correct 187 ms 31072 KB Output is correct
10 Correct 214 ms 30600 KB Output is correct
11 Correct 199 ms 31004 KB Output is correct
12 Correct 189 ms 31188 KB Output is correct
13 Correct 215 ms 30916 KB Output is correct
14 Correct 190 ms 31260 KB Output is correct

Subtask #5
0 / 80.0

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