QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#306732#8050. Random PermutationQingyuCompile Error//C++233.4kb2024-01-17 04:15:342024-01-17 04:15:34

Judging History

你现在查看的是最新测评结果

  • [2024-01-17 04:15:34]
  • 评测
查看
  • [2024-01-17 04:15:34]
  • 提交

answer

#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

#include<bits/stdc++.h>
#define L(i, j, k) for(int i = (j); i <= (k); ++i)
#define R(i, j, k) for(int i = (j); i >= (k); --i)
#define ll long long
#define sz(a) ((int) (a).size())
#define vi vector < int >
#define me(a, x) memset(a, x, sizeof(a))
#define ull unsigned long long
#define ld __float128
#define pb emplace_back
using namespace std;
const int N = 1 << 20, block = 8;
int n;
int p[N], pos[N];
int vis[N];
int tag[N], mx[N], mn[N], lv[N];
inline void upd(int x) {
	mx[x] = max(mx[x * 2], mx[x * 2 + 1]);
	mn[x] = min(mn[x * 2], mn[x * 2 + 1]);
	lv[x] = lv[x * 2];
}
inline void adt(int x, int w) {
	tag[x] += w;
	mx[x] += w;
	mn[x] += w; 
	lv[x] += w;
}
inline void push(int x) {
	if(tag[x]) {
		adt(x * 2, tag[x]);
		adt(x * 2 + 1, tag[x]);
		tag[x] = 0;
	}
}
inline void build(int x, int L, int R) {
	if(L == R) {
		mx[x] = mn[x] = lv[x] = n - L + 1;
		return;
	}
	int mid = (L + R) >> 1;
	build(x * 2, L, mid);
	build(x * 2 + 1, mid + 1, R);
	upd(x);
}
int MX, MN, ls, rs;
inline void query(int x, int L, int R, int l, int r) {
	if(l <= L && R <= r) {
		MN = min(MN, mn[x]);
		MX = max(MX, mx[x]);
		return;
	}
	push(x);
	int mid = (L + R) >> 1;
	if(l <= mid) query(x * 2, L, mid, l, r);
	if(r > mid) query(x * 2 + 1, mid + 1, R, l, r);
}

int sum[N];

ll sc;
inline void make1(int x, int L, int R, int l, int r) {
	if(l <= L && R <= r) {
		if(mx[x] < ls || mn[x] > rs) 
			return ;
		if(R - L + 1 <= block) {
			int cur = lv[x];
			L(i, L, R) {
				if(i > L) {
					if(vis[i]) ++cur;
					else --cur;
				}
				sum[cur] += 1;
			}
			return;
		}
	}
	push(x);
	int mid = (L + R) >> 1;
	if(l <= mid) make1(x * 2, L, mid, l, r);
	if(r > mid) make1(x * 2 + 1, mid + 1, R, l, r);
}
inline void make2(int x, int L, int R, int l, int r) {
	if(l <= L && R <= r) {
		if(mx[x] < ls || mn[x] > rs) 
			return;
		if(R - L + 1 <= block) {
			int cur = lv[x];
			L(i, L, R) {
				if(i > L) {
					if(vis[i]) ++cur;
					else --cur;
				}
				sc += sum[cur] + sum[cur - 1];
			}
			return;
		}
	}
	push(x);
	int mid = (L + R) >> 1;
	if(l <= mid) make2(x * 2, L, mid, l, r);
	if(r > mid) make2(x * 2 + 1, mid + 1, R, l, r);
}
inline void add(int x, int L, int R, int l, int r, int w) {
	if(l <= L && R <= r) {
		adt(x, w);
		return;
	}
	push(x);
	int mid = (L + R) >> 1;
	if(l <= mid) add(x * 2, L, mid, l, r, w);
	if(r > mid) add(x * 2 + 1, mid + 1, R, l, r, w);
	upd(x);
}

mt19937_64 orz;
int main() {
	ios :: sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
//	n = 2e5;
//	L(i, 1, n) 
//		p[i] = i;
//	shuffle(p + 1, p + n + 1, orz);
	cin >> n;
	L(i, 1, n) {
		cin >> p[i];
	}
	
	L(i, 1, n) 
		pos[p[i]] = i; 
	build(1, 0, n);
	
	ll ans = 0; 
	L(i, 1, n) {
		vis[pos[i]] = 1;
		add(1, 0, n, pos[i], n, 2);
		
		MN = 1e9, MX = 0;
		query(1, 0, n, 0, pos[i] - 1);
		int l1 = MN, r1 = MX;
		
		MN = 1e9, MX = 0;
		query(1, 0, n, pos[i], n);
		int l2 = MN, r2 = MX;
		
		ls = max(l1, l2) - 1;
		rs = min(r1, r2) + 1;
		
		sc = 0;
		make1(1, 0, n, 0, pos[i] - 1);
		make2(1, 0, n, pos[i], n);
		
		ls = max(ls - block - 2, 0);
		rs += block + 2;
		L(i, ls, rs) {
			sum[i] = 0;
		}
		ans += sc * i;
	}
	cout << ans << '\n';
	return 0;
}
源文件, 语言: C++23

詳細信息 

In file included from /usr/include/x86_64-linux-gnu/c++/13/bits/gthr.h:148,
                 from /usr/include/c++/13/ext/atomicity.h:35,
                 from /usr/include/c++/13/bits/ios_base.h:39,
                 from /usr/include/c++/13/streambuf:43,
                 from /usr/include/c++/13/bits/streambuf_iterator.h:35,
                 from /usr/include/c++/13/iterator:66,
                 from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:54,
                 from answer.code:5:
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:102:1: error: attribute value ‘tune=native’ was already specified in ‘target’ attribute
  102 | __gthrw(pthread_once)
      | ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:102:1: error: attribute value ‘tune=native’ was already specified in ‘target’ attribute
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:103:1: error: attribute value ‘tune=native’ was already specified in ‘target’ attribute
  103 | __gthrw(pthread_getspecific)
      | ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:103:1: error: attribute value ‘tune=native’ was already specified in ‘target’ attribute
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:104:1: error: attribute value ‘tune=native’ was already specified in ‘target’ attribute
  104 | __gthrw(pthread_setspecific)
      | ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:104:1: error: attribute value ‘tune=native’ was already specified in ‘target’ attribute
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:106:1: error: attribute value ‘tune=native’ was already specified in ‘target’ attribute
  106 | __gthrw(pthread_create)
      | ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:106:1: error: attribute value ‘tune=native’ was already specified in ‘target’ attribute
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:107:1: error: attribute value ‘tune=native’ was already specified in ‘target’ attribute
  107 | __gthrw(pthread_join)
      | ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:107:1: error: attribute value ‘tune=native’ was already specified in ‘target’ attribute
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:108:1: error: attribute value ‘tune=native’ was already specified in ‘target’ attribute
  108 | __gthrw(pthread_equal)
      | ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:108:1: error: attribute value ‘tune=native’ was already specified in ‘target’ attribute
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:109:1: error: attribute value ‘tune=native’ was already specified in ‘target’ attribute
  109 | __gthrw(pthread_self)
      | ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:109:1: error: attribute value ‘tune=native’ was already specified in ‘target’ attribute
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:110:1: error: attribute value ‘tune=native’ was already specified in ‘target’ attribute
  110 | __gthrw(pthread_detach)
      | ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:110:1: error: attribute value ‘tune=native’ was already specified in ‘target’ attribute
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:112:1: error: attribute value ‘tune=native’ was already specified in ‘target’ attribute
  112 | __gthrw(pthread_cancel)
      | ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:112:1: error: attribute value ‘tune=native’ was already specified in ‘target’ attribute
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:114:1: error: attribute value ‘tune=native’ was already specified in ‘target’ attribute
  114 | __gthrw(sched_yield)
      | ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:114:1: error: attribute value ‘tune=native’ was already specified in ‘target’ attribute
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:116:1: error: attribute value ‘tune=native’ was already specified in ‘target’ attribute
  116 | __gthrw(pthread_mutex_lock)
      | ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:116:1: error: attribute value ‘tune=native’ was already specified in ‘target’ attribute
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:117:1: error: attribute value ‘tune=native’ was already specified in ‘target’ attribute
  117 | __gthrw(pthread_mutex_trylock)
      | ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:117:1: error: attribute value ‘tune=native’ was already specified in ‘target’ attribute
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:119:1: error: attribute value ‘tune=native’ was already specified in ‘target’ attribute
  119 | __gthrw(pthread_mutex_timedlock)
      | ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:119:1: error: attribute value ‘tune=native’ was already specified in ‘target’ attribute
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:121:1: error: attribute value ‘t...
English 繁體中文 简体中文

伺服器時間: 2025-02-02 13:50:57 | 開源專案