oj.uz

Submission #203366

# Submission time Handle Problem Language Result Execution time Memory
203366 2020-02-20T11:29:04 Z Bruteforceman Fire (JOI20_ho_t5) C++11
0 / 100
 1000 ms 37264 KB 
#include <bits/stdc++.h>
using namespace std;
#define prev previous
const int maxn = 200005;
using pii = pair <int, int>;

int n;
int s[maxn];
struct query {
	int l, r, t;
} Q[maxn];
vector <int> v[maxn];
int prev[maxn];
int l[maxn], r[maxn];
vector <int> g[maxn];
int sub[maxn];
long long t[maxn];
long long pred[maxn];

void eulerOrder(int x) {
	static int current = 0;
	l[x] = ++current;
	for(int i : g[x]) {
		eulerOrder(i);
		pred[i] = sub[x];
		sub[x] += sub[i]; 
	}
	sub[x] += 1;
	r[x] = current;
}
void update(int x, long long val) {
	for(int i = x; i <= n + 1; i += i & (-i)) {
		t[i] += val;
	}
}
long long sum(int x) {
	long long ans = 0;
	for(int i = x; i > 0; i -= i & (-i)) {
		ans += t[i];
	}
	return ans;
}

int main() {
	int q;
	scanf("%d %d", &n, &q);
	for_each(s + 1, s + n + 1, [] (int &i) { scanf("%d", &i); });
	for_each(Q + 1, Q + q + 1, [&] (query &i) { 
					scanf("%d %d %d", &i.t, &i.l, &i.r); 
					v[i.r].emplace_back(i.t);
					v[i.l - 1].emplace_back(i.t); });
	stack <int> st;
	for(int i = 1; i <= n; i++) {
		while(!st.empty() && s[st.top()] < s[i]) {
			st.pop();
		} 
		prev[i] = st.empty() ? 0 : st.top();
		st.push(i);
	}
	for(int i = 1; i <= n; i++) {
		g[prev[i]].push_back(i);
	}
	eulerOrder(0);
	map <pii, long long> res;
	auto cost = [&] (int x) {
		if(prev[x] == 0) return 0;
		else return s[prev[x]] - s[x];
	};
	vector <int> rmq;
	for(int i = 1; i <= n; i++) {
		while(!rmq.empty() && s[rmq.back()] < s[i]) {
			rmq.pop_back();
		}
		rmq.push_back(i);
		for(int t : v[i]) {
			int last = *lower_bound(rmq.begin(), rmq.end(), i - t);
			long long ans = s[last] * (i - last);
			// cout << s[last] << endl;
			for(int k = 1; k <= last; k++) {
				int var = t - pred[k];
				var = min(var, sub[k]);
				var = max(var, 0);
				ans += 1LL * cost(k) * var;
				ans += s[k];
			}
			res[pii(i, t)] = ans;
		}
	}
	for_each(Q + 1, Q + q + 1, [&] (query i) { 
				printf("%lld\n", res[pii(i.r, i.t)] - res[pii(i.l - 1, i.t)]); });
	return 0;
}

Compilation message

ho_t5.cpp: In function 'int main()':
ho_t5.cpp:46:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &n, &q);
  ~~~~~^~~~~~~~~~~~~~~~~
ho_t5.cpp: In lambda function:
ho_t5.cpp:47:48: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for_each(s + 1, s + n + 1, [] (int &i) { scanf("%d", &i); });
                                           ~~~~~^~~~~~~~~~
ho_t5.cpp: In lambda function:
ho_t5.cpp:49:11: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
      scanf("%d %d %d", &i.t, &i.l, &i.r); 
      ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 1.0

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

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 9720 KB Output is correct
2 Execution timed out 1091 ms 27172 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 9720 KB Output is correct
2 Execution timed out 1090 ms 29032 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 6.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1096 ms 37264 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 80.0

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