fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long
  4. #define f(i, x, n) for(int i = x; i < (int)(n); ++i)
  5.  
  6. int w[200001], tmp[200001];
  7. pair<int, pair<int, bool> > ev[400000];
  8.  
  9. int main(){
  10. 	int n, m;
  11. 	scanf("%d%d", &n, &m);
  12. 	f(i, 1, n + 1)scanf("%d", tmp + i);
  13. 	int j = 1;
  14. 	while (tmp[j])++j;
  15. 	if (++j == n + 1)j = 1;
  16. 	f(i, 1, n + 1)w[i] = tmp[(i + j - 2) % n + 1];
  17. 	f(i, 0, m){
  18. 		int l, r;
  19. 		scanf("%d%d", &l, &r);
  20. 		if ((l -= j - 1) <= 0)l += n;
  21. 		if ((r -= j - 1) <= 0)r += n;
  22. 		if (l > r)swap(l, r);
  23. 		ev[i << 1] = make_pair(l, make_pair(l, false));
  24. 		ev[i << 1 | 1] = make_pair(r, make_pair(l, true));
  25. 	}
  26. 	sort(ev, ev + (m << 1));
  27. 	deque<pair<ll, int> > q1, q2;
  28. 	q1.push_back(make_pair(0, 1));
  29. 	q2.push_back(make_pair(0, 1));
  30. 	m <<= 1;
  31. 	j = 0;
  32. 	int a = 1, b = 1;
  33. 	f(i, 1, n){
  34. 		while (j < m && ev[j].first <= i){
  35. 			if (ev[j].second.second)b = max(b, ev[j].second.first + 1);
  36. 			else a = max(a, ev[j].second.first + 1);
  37. 			++j;
  38. 		}
  39. 		while (!q1.empty() && q1.front().second < a)q1.pop_front();
  40. 		while (q2.front().second < b)q2.pop_front();
  41. 		ll an = w[i] + q2.front().first;
  42. 		if (!q1.empty())an = min(an, q1.front().first);
  43. 		while (!q1.empty() && q1.back().first >= an)q1.pop_back();
  44. 		q1.push_back(make_pair(an, i + 1));
  45. 		while (!q2.empty() && q2.back().first >= an)q2.pop_back();
  46. 		q2.push_back(make_pair(an, i + 1));
  47. 	}
  48. 	printf("%lld\n", q2.back().first);
  49. }
Success #stdin #stdout 0s 22320KB
comments (?)
stdin
copy 
4 2
1 0 1 1
1 4
2 3
stdout
copy 
1
https://ideone.com/F0IAal
language:
C++14 (gcc 8.3)
created:
7 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!