Submission #51471326

---

Source Code Expand

// LUOGU_RID: 151826033
// Author: gsczl71
// Copyright (c) 2024 gsczl71 All rights reserved.
// Problem: E - LEQ
// Contest: AtCoder - AtCoder Beginner Contest 221
// URL: https://atcoder.jp/contests/abc221/tasks/abc221_e
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
// Date: 2024-03-19 16:33:46

// #pragma GCC optimize(2,3,"Ofast","inline")
#include<bits/stdc++.h>
#define ll long long
#define i128 __int128
#define ull unsigned long long
#define pii pair<int,int>
#define pll pair<long long, long long>
#define fs first
#define sc second
#define x0 _x0_
#define y1 _y1_
#define endl '\n'
#define re register
#define pb push_back
#define vi vector<int>
#define pq priority_queue
#define mem(a,x) memset((a),(x),sizeof(a))
#define debug puts("AK IOI")
#define sz(s) (int)(s.size())
#define all(a) a.begin(),a.end()
#define rd(l,r) (myrand()%(r-l+1)+l)
#define print(x) {cout<<x<<endl;return;}
#define ctn(e) if(e) continue
#define brk(e) if(e) break
#define rt(e) if(e) return
#define ll_(e) (1ll*(e))
#define For(x,y,z) for(int x = y;x <= z;x++)
#define For_(x,y,z) for(int x = y;x <= z;x--)
#define lowbit(x) (x&(-x))
using namespace std;
#define int long long
// const int mod = 1e9+7;
const int mod = 998244353;
mt19937 myrand(time(0));
const int inf = 0x3f3f3f3f,N = 3e5+5,M = 1e6+5,K = 3000+5;
const long long linf = 0x3f3f3f3f3f3f3f3f;
int n,a[N],b[N],m;
int res=0;
int t[N];
int ksm(int a,int b){
	int res=1;
	while(b){
		if(b&1) {res *= a;res %= mod;}
		a=a*a,a%=mod;
		b>>=1;
	} return res;
}void modify(int x,int v){
	for(int i = x;i <= n;i += lowbit(i)) t[i] = (t[i] + v) % mod;
}int query(int x){
	int res=0;
	for(int i = x;i >= 1;i -= lowbit(i)) res = (res + t[i]) % mod;
	return res;
}
void solve(){
	cin>>n;For(i,1,n)b[i]=((cin>>a[i]),a[i]);
	sort(b+1,b+1+n);
	m=unique(b+1,b+1+n)-b-1;
	For(i,1,n) a[i]=lower_bound(b+1,b+1+m,a[i])-b;
	For(i,1,n) {
		res += 	query(a[i]) * ksm(2,i-1) % mod;
		res %= mod;
		modify(a[i],ksm((mod+1>>1),i));
	}cout<<res<<endl;
}
signed main(){
	ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
	int T=1;
//	cin >> T;
	For(_,1,T) solve();
	return 0;
}

Submission Info

Compile Error

Main.cpp: In function ‘void solve()’:
Main.cpp:72:37: warning: suggest parentheses around ‘+’ inside ‘>>’ [-Wparentheses]
   72 |                 modify(a[i],ksm((mod+1>>1),i));
      |                                  ~~~^~

Judge Result