結果
| 問題 | No.694 square1001 and Permutation 3 |
| ユーザー |
 Lugh
|
| 提出日時 | 2021-05-13 19:50:58 |
| 言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 15,414 bytes |
| コンパイル時間 | 2,212 ms |
| コンパイル使用メモリ | 192,052 KB |
| 実行使用メモリ | 22,936 KB |
| 最終ジャッジ日時 | 2024-09-25 08:03:58 |
| 合計ジャッジ時間 | 10,309 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge4 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 2 ms
5,248 KB |
| testcase_01 | WA | - |
| testcase_02 | WA | - |
| testcase_03 | WA | - |
| testcase_04 | WA | - |
| testcase_05 | WA | - |
| testcase_06 | WA | - |
| testcase_07 | WA | - |
| testcase_08 | WA | - |
| testcase_09 | WA | - |
| testcase_10 | WA | - |
| testcase_11 | WA | - |
| testcase_12 | WA | - |
| testcase_13 | AC | 2 ms
5,376 KB |
ソースコード
#include <bits/stdc++.h>
namespace clibrary{
using namespace std;
namespace macro{
using ll=long long;
using ld=long double;
#define rep(i,n) for(ll i=0;i<n;i++)
#define irep(i,n) for(ll i=0;i<=n;i++)
#define reps(i,j,n) for(ll i=j;i<n;i++)
#define repr(i,n) for(ll i=n-1;i>=0;i--)
#define bit(i,n) for(ll i=0;i<(1<<n);i++)
#define dbl(i) fixed << setprecision(15) << i << endl
#define all(a) a.begin(),a.end()
#define gcd __gcd
#define Unweightgraph vector<vector<ll>>
#define Weightgraph vector<vector<Edge>>
#define st(a) sort(a.begin(),a.end())
#define rst(a) sort(a.rbegin(),a.rend())
#define mp(a,b) make_pair(a,b)
#define pb(a) push_back(a)
#define fi first
#define se second
using vl =vector<ll>;
using vi =vector<int>;
using vs =vector<string>;
using vpl =vector<pair<ll,ll>>;
using P=pair<ll,ll>;
const ll mod = 1000000007;
const ll mod1=998244353;
const ll inf=1e9;
const ll linf=1e18;
string yn(bool a){
if(a)return "Yes";
return "No";
}
string Yn(bool a){
if(a)return "YES";
return "NO";
}
template <typename T>
bool chmin(T &a, const T &b) {
if (a > b) {
a = b;
return true;
}
return false;
}
template <typename T>
bool chmax(T &a, const T& b) {
if (a < b) {
a = b;
return true;
}
return false;
}
class mint {
ll x;
public:
mint(ll x=0) : x((x%mod+mod)%mod) {}
mint operator-() const {
return mint(-x);
}
mint& operator+=(const mint& a) {
if ((x += a.x) >= mod) x -= mod;
return *this;
}
mint& operator-=(const mint& a) {
if ((x += mod-a.x) >= mod) x -= mod;
return *this;
}
mint& operator*=(const mint& a) {
(x *= a.x) %= mod;
return *this;
}
mint operator+(const mint& a) const {
mint res(*this);
return res+=a;
}
mint operator-(const mint& a) const {
mint res(*this);
return res-=a;
}
mint operator*(const mint& a) const {
mint res(*this);
return res*=a;
}
mint pow(ll t) const {
if (!t) return 1;
mint a = pow(t>>1);
a *= a;
if (t&1) a *= *this;
return a;
}
// for prime mod
mint inv() const {
return pow(mod-2);
}
mint& operator/=(const mint& a) {
return (*this) *= a.inv();
}
mint operator/(const mint& a) const {
mint res(*this);
return res/=a;
}
friend ostream& operator<<(ostream& os, const mint& m){
os << m.x;
return os;
}
};
class UnionFind {
public:
vector <ll> par; // 各元の親を表す配列
vector <ll> siz; // 素集合のサイズを表す配列(1 で初期化)
UnionFind(ll sz_): par(sz_), siz(sz_, 1LL) {
for (ll i = 0; i < sz_; ++i) par[i] = i; // 初期では親は自分自身
}
void init(ll sz_) {
par.resize(sz_);
siz.assign(sz_, 1LL); // resize だとなぜか初期化されなかった
for (ll i = 0; i < sz_; ++i) par[i] = i; // 初期では親は自分自身
}
ll root(ll x) { // 根の検索
while (par[x] != x) {
x = par[x] = par[par[x]]; // x の親の親を x の親とする
}
return x;
}
bool unite(ll x, ll y) {
x = root(x);
y = root(y);
if (x == y) return false;
// merge technique（データ構造をマージするテク．小を大にくっつける）
if (siz[x] < siz[y]) swap(x, y);
siz[x] += siz[y];
par[y] = x;
return true;
}
bool same(ll x, ll y) { // 連結判定
return root(x) == root(y);
}
ll size(ll x) { // 素集合のサイズ
return siz[root(x)];
}
};
struct Edge {
ll to; // 辺の行き先
ll weight; // 辺の重み
Edge(ll t, ll w) : to(t), weight(w) { }
};
//バイナリーインデックスツリー
template<typename T>
class BIT{
public:
int N;
vector<T> data;
BIT(T _N):N(_N){
data.assign(N+1, 0);
};
// a is 1-indexed
void add1(int a, T w){
for(int x = a; x <= N; x += x & -x)data[x] += w;
}
// 1-indexed sum of prefix [0, a]
T sum1(int a){
T res = 0;
for(int x = a; x > 0; x -= x & -x)res += data[x];
return res;
}
// 1-indexed sum of range [l, r]
T sum1(int l, int r){return sum1(r) - sum1(l-1);}
// 0-indexed add
void add(int a, T w){add1(a + 1, w);}
// 0-indexed sum
T sum(int a){return sum1(a + 1);}
// 0-indexed sum of range
T sum(int l, int r){return sum(r) - sum(l-1);}
// show the value
void debug(){print(data);}
};
//区間加算BIT
template <typename T>
struct BIT2 {
int n; // 要素数
vector<T> bit[2]; // データの格納先
BIT2(int n_) { init(n_); }
void init(int n_) {
n = n_ + 1;
for (int p = 0; p < 2; p++) bit[p].assign(n, 0);
}
void add_sub(int p, int i, T x) {
for (int idx = i; idx < n; idx += (idx & -idx)) {
bit[p][idx] += x;
}
}
void add(int l, int r, T x) { // [l,r) に加算
add_sub(0, l, -x * (l - 1));
add_sub(0, r, x * (r - 1));
add_sub(1, l, x);
add_sub(1, r, -x);
}
T sum_sub(int p, int i) {
T s(0);
for (int idx = i; idx > 0; idx -= (idx & -idx)) {
s += bit[p][idx];
}
return s;
}
T sum(int i) { return sum_sub(0, i) + sum_sub(1, i) * i; }
};
struct Edge3 {
ll cost, from, to;
Edge3() {}
Edge3(ll c, ll f, ll t) : from(c), to(f), cost(t) {}
friend bool operator < (const Edge3& lhs, const Edge3& rhs) { return lhs.cost < rhs.cost; };
friend bool operator > (const Edge3& lhs, const Edge3& rhs) { return rhs < lhs; };
friend bool operator <= (const Edge3& lhs, const Edge3& rhs) { return !(lhs > rhs); };
friend bool operator >= (const Edge3& lhs, const Edge3& rhs) { return !(lhs < rhs); };
};
struct kruskal{
struct UnionFind uf;
uint64_t weight; // 最小全域木の辺の重みの和
kruskal(ll V, vector<Edge3> &edges) : uf(V), weight(0) {
sort(edges.begin(), edges.end());
for (auto e : edges) {
if (uf.same(e.from, e.to)) continue;
uf.unite(e.from, e.to);
weight += e.cost;
}
}
};
}
using namespace macro;
//約数列挙
vector<ll> enum_divisors(ll N) {
vector<ll> res;
for (ll i = 1; i * i <= N; ++i) {
if(N % i == 0) {
res.push_back(i);
if (N/i != i) res.push_back(N/i);
}
}
sort(res.begin(), res.end());
return res;
}
//素数チェック
bool prime(ll a){
if(a<=1)return false;
for(int i=2;i*i<=a;i++){
if(a%i==0)return false;
}
return true;
}
//最小公倍数
ll lcm(ll a,ll b){
ll d = gcd(a,b);
return a/d*b;
}
//aのn乗(繰り返し二乗法)
template <typename T>
T rui(T a, T n){
T x = 1;
while(n > 0){//全てのbitが捨てられるまで。
if(n&1){//1番右のbitが1のとき。
x = x*a;
}
a = a*a;
n >>= 1;//bit全体を右に1つシフトして一番右を捨てる。
}
return x;
}
//xのn乗(mod)
long long mpow(long long x, long long n,ll m) {
ll ret=1;
while (n > 0) {
if (n & 1) ret =ret*x % m; // n の最下位bitが 1 ならば x^(2^i) をかける
x = x * x % m;
n >>= 1; // n を1bit 左にずらす
}
return ret;
}
//nCr
vector<vector<ll>> comblist(int n, int r) {
vector<vector<ll>> v(n + 1,vector<ll>(n + 1, 0));
for (int i = 0; i < v.size(); i++) {
v[i][0] = 1;
v[i][i] = 1;
}
for (int j = 1; j < v.size(); j++) {
for (int k = 1; k < j; k++) {
v[j][k] = (v[j - 1][k - 1] + v[j - 1][k]);
}
}
return v;
}
//nCr (mod)
ll mcomb(ll n,ll x,ll mod){
ll res;
ll a=1;
for(ll i=0;i<x;i++){
a=a*n%mod;
n--;
}
ll b=1;
for(ll i=1;i<x+1;i++)
{
b=b*i%mod;
}
res=(a*mpow(b,mod-2,mod))%mod;
return res;
}
//φ関数(1からnまでのうちnと互いな素な個数)
ll phi(ll n){
ll ret =n;
for(ll i = 2; i * i <= n; i++) {
if(n % i == 0) {
ret -= ret / i;
while(n % i == 0) n /= i;
}
}
if(n>1)ret -=ret/n;
return ret;
}
//拡張ユークリッド互助法
ll extGCD(ll a, ll b, ll &x, ll &y) {
if (b == 0) {
x = 1;
y = 0;
return a;
}
ll d = extGCD(b, a%b, y, x); // 再帰的に解く
y -= a / b * x;
return d;
}
//逆元
ll modinv(ll a, ll m) {
ll x, y;
extGCD(a, m, x, y);
return (x % m + m) % m;
}
//ビット本数
ll bcount(ll bits){
bits = (bits & 0x55555555) + (bits >> 1 & 0x55555555);
bits = (bits & 0x33333333) + (bits >> 2 & 0x33333333);
bits = (bits & 0x0f0f0f0f) + (bits >> 4 & 0x0f0f0f0f);
bits = (bits & 0x00ff00ff) + (bits >> 8 & 0x00ff00ff);
return (bits & 0x0000ffff) + (bits >>16 & 0x0000ffff);
}
//素因数分解
vector<pair<long long, long long> > prime_factorize(long long N) {
vector<pair<long long, long long> > res;
for (long long a = 2; a * a <= N; ++a) {
if (N % a != 0) continue;
long long ex = 0; // 指数
// 割れる限り割り続ける
while (N % a == 0) {
++ex;
N /= a;
}
// その結果を push
res.push_back({a, ex});
}
// 最後に残った数について
if (N != 1) res.push_back({N, 1});
return res;
}
//ワーシャルフロイド法(iからjに行くまでの最小コスト計算,nは要素数,dはコスト表)
void warshall_floyd(int n,vector<vector<ll>> &d){
for (int k = 0; k < n; k++){ // 経由する頂点
for (int i = 0; i < n; i++) { // 始点
for (int j = 0; j < n; j++) { // 終点
d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
}
}
}
}
//エラトステネスのふるい(n以下の素数列挙)
vector<ll> eratosthenes( const ll N ){
vector<bool> is_prime( N + 1 );
for( ll i = 0; i <= N; i++ )
{
is_prime[ i ] = true;
}
vector<ll> P;
for( ll i = 2; i <= N; i++ )
{
if( is_prime[ i ] )
{
for( ll j = 2 * i; j <= N; j += i )
{
is_prime[ j ] = false;
}
P.emplace_back( i );
}
}
return P;
}
//エラトステネスのふるい(素数チェック)
vector<bool> eratosthenescheck( const ll N ){
vector<bool> is_prime( N + 1 );
for( ll i = 0; i <= N; i++ )
{
is_prime[ i ] = true;
}
for( ll i = 2; i <= N; i++ )
{
if( is_prime[ i ] )
{
for( ll j = 2 * i; j <= N; j += i )
{
is_prime[ j ] = false;
}
}
}
return is_prime;
}
//ダイクストラ
vector<ll> dijkstra(ll s,ll n,vector<vector<Edge>> g){
priority_queue<P, vector<P>, greater<P>> q;
vector<ll> dist(n,linf);
q.push(make_pair(0, s));
dist[s] = 0;
while (!q.empty()) {
ll pos = q.top().second;
ll cost=q.top().first;
q.pop();
if(cost>dist[pos])continue;
for (ll i = 0; i < g[pos].size(); i++) {
ll to = g[pos][i].to, cost = g[pos][i].weight;
if (dist[to] > dist[pos] + cost) {
dist[to] = dist[pos] + cost;
q.push(make_pair(dist[to], to));
}
}
}
return dist;
}
//区間素数(l=b-a+1)
ll sieve(ll a,ll b){
ll x=sqrt(b);
ll l=b-a+1;
vector<bool> pri(x,true);
vector<bool> ans(l,true);
for(ll i=2;i*i<b;i++){
if(pri[i]){
for(ll j=2*i;j*j<b;j+=i)pri[j]=false;
for(ll j=max(2LL,(a+i-1)/i)*i;j<b;j+=i)ans[j-a]=false;
}
}
ll tmp=0;
rep(i,b-a)if(ans[i])tmp++;
return tmp;
}
}
using namespace clibrary;
int main(){
ll n;
cin >> n;
vl a(n);
vector<ll> x(n);
rep(i,n){
cin >> a[i];
x[i]=a[i];
}
st(x);
x.erase(unique(all(x)),x.end());
vector<ll> dp(n+10,0),cnt(n+2,0);
rep(i,n){
a[i]=lower_bound(all(x),a[i])-x.begin();
dp[a[i]]++;
}
rep(i,n){
cnt[i+1]=cnt[i]+dp[i];
}
BIT<ll> g(n+1);
ll ans=0;
rep(i,n){
ans+=g.sum(a[i]+1);
g.add(a[i]+1,1);
}
rep(i,n){
cout << ans<<endl;
ans=ans-cnt[a[i]]+(n-cnt[a[i]+1]);
}
}