Submission #1685540


Source Code Expand

#include <iostream>
#include <iomanip>
#include <string>
#include <vector>
#include <queue>
#include <algorithm>
#include <utility>
#include <cmath>
#include <map>
#include <set>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <cstring>
using namespace std;

#define INF_LL (ll)1e18
#define INF (int)1e9
#define REP(i, n) for(int i = 0;i < (n);i++)
#define FOR(i, a, b) for(int i = (a);i < (b);i++)
#define all(x) x.begin(),x.end()
using ll = long long;
using PII = pair<int, int>;

const double eps = 1e-10;

template<typename A, typename B>inline void chmin(A &a, B b){if(a > b) a = b;}
template<typename A, typename B>inline void chmax(A &a, B b){if(a < b) a = b;}

class RMQ{
private:
	int n;
	vector<ll> node, lazy;
	vector<bool> lazyFlag;
public:
	RMQ(vector<ll> v){
		int sz = v.size();
		n = 1; while(n < sz) n *= 2;
		node.resize(2*n-1, INF_LL);
		lazy.resize(2*n-1, 0);
		lazyFlag.resize(2*n-1, false);
		REP(i, sz) node[i+n-1] = INF_LL;
		for(int i = n-2;i >= 0;i--) node[i] = min(node[2*i+1], node[2*i+2]);
	}

	void eval(int k, int l, int r){
		if(lazyFlag[k]){
			node[k] = lazy[k];
			if(r-l > 1){
				lazy[2*k+1] = lazy[k];
				lazy[2*k+2] = lazy[k];
				lazyFlag[2*k+1] = lazyFlag[2*k+2] = true;
			}
			lazy[k] = 0;
			lazyFlag[k] = false;
		}
	}

	void update(int a, int b, ll x, int k=0, int l=0, int r=-1){
		if(r < 0) r = n;
		eval(k, l, r);
		if(b <= l || r <= a) return;

		if(a <= l && r <= b){
			lazy[k] = x;
			lazyFlag[k] = true;
			eval(k, l, r);
		}else{
			update(a, b, x, k*2+1, l, (l+r)/2);
			update(a, b, x, k*2+2, (l+r)/2, r);
			node[k] = min(node[k*2+1], node[k*2+2]);
		}
	}

	ll query(int a, int b, int k=0, int l=0, int r=-1){
		if(r < 0) r = n;
		eval(k, l, r);

		if(b <= l || r <= a) return INF_LL;
		if(a <= l && r <= b) return node[k];

		return min(query(a, b, k*2+1, l, (l+r)/2), query(a, b, k*2+2, (l+r)/2, r));
	}
};

int main(void){
	int N;
	ll res = 0;
	cin >> N;
	vector<ll> v(N);
	RMQ rmq(v);
	int in[114514];
	REP(i, N){
		int a;
		cin >> a; a--;
		in[a] = i;
	}

	REP(i, N){
		int la, ra;
		int l = 0, r = in[i]+1, m;
		while(r-l > 1){
			m = (l+r)/2;

			if(rmq.query(m, r+1) == INF_LL){
				r = m;
			}else{
				l = m;
			}
		}
		if(rmq.query(l, l+1) == INF_LL)
			la = l;
		else
			la = r;
		l = in[i]; r = N;
		while(r-l > 1){
			m = (l+r)/2;

			if(rmq.query(l, m+1) == INF_LL){
				l = m;
			}else{
				r = m;
			}
		}
		ra = l;
		rmq.update(in[i], in[i]+1, 0);
		cout << la << " " << ra << endl;
		res += (ll)(in[i]-la+1)*(ll)(ra-in[i]+1)*(i+1);
	}
	cout << res << endl;
}

Submission Info

Submission Time
Task B - Minimum Sum
User maze1230
Language C++14 (GCC 5.4.1)
Score 0
Code Size 2683 Byte
Status RE
Exec Time 137 ms
Memory 11648 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 400
Status
WA × 3
WA × 7
RE × 6
Set Name Test Cases
Sample example0, example1, example2
All corner0, corner1, corner2, corner3, example0, example1, example2, maxrand0, maxrand1, maxrand2, rand0, rand1, rand2
Case Name Status Exec Time Memory
corner0 RE 137 ms 11648 KB
corner1 RE 106 ms 11648 KB
corner2 WA 1 ms 256 KB
corner3 RE 121 ms 11648 KB
example0 WA 1 ms 256 KB
example1 WA 1 ms 256 KB
example2 WA 1 ms 256 KB
maxrand0 RE 104 ms 11648 KB
maxrand1 RE 104 ms 11648 KB
maxrand2 RE 104 ms 11648 KB
rand0 WA 2 ms 256 KB
rand1 WA 1 ms 256 KB
rand2 WA 1 ms 256 KB