Submission #203435

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
203435	2020-02-20T16:15:20 Z	Bruteforceman	Fire (JOI20_ho_t5)	C++11	Compilation error	0 ms	0 KB

ho_t5

#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];
vector <int> g[maxn];
int sub[maxn];
long long pred[maxn];
long long pref[maxn];
long long res[maxn];
vector <int> h[maxn];

void eulerOrder(int x) {
	for(int i : g[x]) {
		eulerOrder(i);
		pred[i] = sub[x];
		sub[x] += sub[i]; 
	}
	sub[x] += 1;
}
struct BinaryIndexedTree {
	long long t[maxn]; 
	int size;
	void update(int x, long long val) {
		x += 1;
		for(int i = x; i <= size + 1; i += i & (-i)) {
			t[i] += val;
		}
	}
	long long sum(int x) {
		x = min(x, size);
		x += 1;
		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);  });
	for(int i = 1; i <= q; i++) {
		v[Q[i].l - 1].push_back(-i);
		v[Q[i].r].push_back(i);
	}
	for(int i = 1; i <= n; i++) {
		pref[i] = pref[i - 1] + s[i];
	}
	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);
	auto cost = [&] (int &x) {
		if(prev[x] == 0) return 0;
		else return s[prev[x]] - s[x];
	};
	BinaryIndexedTree A, B, C, D;
	A.size = B.size = C.size = D.size = n;
	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(auto j : v[i]) {
			int id = j;
			int t = Q[abs(id)].t;
			int last = *lower_bound(rmq.begin(), rmq.end(), i - t);
			long long add = 1LL * s[last] * (i - last) + pref[last];
			h[last].emplace_back(id);
			if(id < 0) res[-id] -= add;
			else res[id] += add;
		}
	}
	for(int i = 1; i <= n; i++) {
		int k = i;
		A.update(pred[k], 1LL * cost(k) * pred[k]);
		B.update(pred[k], 1LL * cost(k));
		C.update(pred[k] + sub[k], 1LL * cost(k) * (sub[k] + pred[k]));
		D.update(pred[k] + sub[k], 1LL * cost(k));	
		for(auto j : h[i]) {
			int id = j;
			int t = Q[abs(id)].t;
			long long add = 0;
			add += B.sum(t) * t - A.sum(t);
			add += C.sum(t) - D.sum(t) * t;
			if(id < 0) res[-id] -= add;
			else res[id] += add;
		}
	}
	for_each(res + 1, res + q + 1, [] (auto &i) { printf("%lld\n", i); } );
	return 0;
}

Compilation message

ho_t5.cpp: In function 'int main()':
ho_t5.cpp:110:37: error: use of 'auto' in lambda parameter declaration only available with -std=c++14 or -std=gnu++14
  for_each(res + 1, res + q + 1, [] (auto &i) { printf("%lld\n", i); } );
                                     ^~~~
ho_t5.cpp: In lambda function:
ho_t5.cpp:110:66: warning: format '%lld' expects argument of type 'long long int', but argument 2 has type 'int' [-Wformat=]
  for_each(res + 1, res + q + 1, [] (auto &i) { printf("%lld\n", i); } );
                                                                 ~^
In file included from /usr/include/c++/7/algorithm:62:0,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:65,
                 from ho_t5.cpp:1:
/usr/include/c++/7/bits/stl_algo.h: In instantiation of '_Funct std::for_each(_IIter, _IIter, _Funct) [with _IIter = long long int*; _Funct = main()::<lambda(int&)>]':
ho_t5.cpp:110:71:   required from here
/usr/include/c++/7/bits/stl_algo.h:3884:5: error: no match for call to '(main()::<lambda(int&)>) (long long int&)'
  __f(*__first);
  ~~~^~~~~~~~~~
/usr/include/c++/7/bits/stl_algo.h:3884:5: note: candidate: void (*)(int&) <conversion>
/usr/include/c++/7/bits/stl_algo.h:3884:5: note:   conversion of argument 2 would be ill-formed:
/usr/include/c++/7/bits/stl_algo.h:3884:5: error: cannot bind non-const lvalue reference of type 'int&' to an rvalue of type 'int'
ho_t5.cpp:110:44: note: candidate: main()::<lambda(int&)> <near match>
  for_each(res + 1, res + q + 1, [] (auto &i) { printf("%lld\n", i); } );
                                            ^
ho_t5.cpp:110:44: note:   conversion of argument 1 would be ill-formed:
In file included from /usr/include/c++/7/algorithm:62:0,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:65,
                 from ho_t5.cpp:1:
/usr/include/c++/7/bits/stl_algo.h:3884:5: error: cannot bind non-const lvalue reference of type 'int&' to an rvalue of type 'int'
  __f(*__first);
  ~~~^~~~~~~~~~
ho_t5.cpp: In function 'int main()':
ho_t5.cpp:49: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:50: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:52: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);  });
      ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~