結果

問題 No.2374 ASKT Subsequences
ユーザー Yoyoyo8128Yoyoyo8128
提出日時 2023-07-07 23:16:14
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 45 ms / 2,000 ms
コード長 8,258 bytes
コンパイル時間 2,905 ms
コンパイル使用メモリ 210,216 KB
実行使用メモリ 34,944 KB
最終ジャッジ日時 2024-07-21 19:40:37
合計ジャッジ時間 3,662 ms
ジャッジサーバーID
(参考情報)
judge3 / judge4
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 3
other AC * 28
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using pii = pair<int, int>;
using pli = pair<ll, int>;
using pll = pair<ll, ll>;
using Graph = vector<vector<ll>>;
const string Yes="Yes";
const string No="No";
const string YES="YES";
const string NO="NO";
const string abc="ABCDEFGHIJKLMNOPQRSTUVWXYZ";
const ll MOD=1000000007;
const ll mod=998244353;
const long long INF = 1LL << 60;
const long double PI=3.141592653589793;
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(), (x).end()
#define fi first
#define se second
#define YESNO(T) if(T){cout<<"YES"<<endl;}else{cout<<"NO"<<endl;}
#define yesno(T) if(T){cout<<"yes"<<endl;}else{cout<<"no"<<endl;}
#define YesNo(T) if(T){cout<<"Yes"<<endl;}else{cout<<"No"<<endl;}
#define inV(vec) for(ll i=0;i<vec.size();i++)cin>>vec[i];
#define outV(vec) for(ll i=0;i<vec.size();i++){cout<<vec[i]<<" ";}cout<<endl;
#define print(s) cout<<s<<endl;
template <typename T>
inline bool chmax(T &a, T b) { return ((a < b) ? (a = b, true) : (false)); }
template <typename T>
inline bool chmin(T &a, T b) { return ((a > b) ? (a = b, true) : (false)); }
//DFS
map<ll,vector<int>>Gra;
map<ll,ll>visited;// false=not visited, true=visited
ll hen=0;
void DFS(int pos){
visited[pos]=true;
for(int i : Gra[pos]){
if(visited[i]==false)DFS(i);
}
}
//BFS
const vector<int>dx = {0, 1, 0, -1};
const vector<int>dy = {1, 0, -1, 0};
vector<vector<int>> BFS(int H, int W, const vector<string> &G, pair<int, int> s) {
vector<vector<int>> dist(H, vector<int>(W, -1)); //
queue<pair<int, int>> que;
// (s)
dist[s.first][s.second] = 0;
que.push(s); // s
// BFS
while (!que.empty()) {
pair<int, int> v = que.front();
que.pop();
//v調
for (int i = 0; i < 4; i++) {
int X = dx[i] + v.first;
int Y = dy[i] + v.second;
if (X < 0 || X >= H || Y < 0 || Y >= W) continue;
//
if (dist[X][Y] != -1 || G[X][Y] == '#') continue;
//x
dist[X][Y] = dist[v.first][v.second] + 1;
que.push(make_pair(X, Y));
}
}
return dist;
}
//
vector<bool>Prime(2,false);//false=not Prime number, true=Prime Number
void Era(ll N){
for(ll i=0;i<N-1;i++){
Prime.pb(true);
}
for(ll i=2;i*i<=N;i++){
if(Prime[i]){
for(ll x=2*i;x<=N;x+=i)Prime[x]=false;
}
}
}
//
ll modpow(ll a, ll n, ll mod) {
if(a==0){
return 0;
}
ll res = 1;
while (n > 0) {
if (n & 1) res = res * a % mod;
a = a * a % mod;
n >>= 1;
}
return res;
}
//
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;
}
//
ll Div(ll a,ll b,ll m){
return (a * modpow(b,m-2,m)) % m;
}
//
vector<ll>fact(1);
void fac(ll N,ll m){
fact[0]=1;
for(int i=1;i<=N;i++){
fact.pb(fact[i-1]*(i));
fact[i]%=m;
}
}
//
ll comb(ll n,ll r,ll m){
return Div(fact[n],fact[r] * fact[n-r] % m,m);
}
//UnionFind
struct UnionFind {
vector<int> par, rank, siz;
//
UnionFind(int n) : par(n,-1), rank(n,0), siz(n,1) { }
//
int root(int x) {
if (par[x]==-1) return x; // x x
else return par[x] = root(par[x]); //
}
// x y (= )
bool same(int x, int y) {
return root(x)==root(y);
}
// x y
bool unite(int x, int y) {
int rx = root(x), ry = root(y); // x y
if (rx==ry) return false; //
// union by rank
if (rank[rx]<rank[ry]) swap(rx, ry); // ry rank
par[ry] = rx; // ry rx
if (rank[rx]==rank[ry]) rank[rx]++; // rx rank 調
siz[rx] += siz[ry]; // rx siz 調
return true;
}
// x
int size(int x) {
return siz[root(x)];
}
};
//https://algo-method.com/descriptions/136
//
struct Edge {
long long to;
long long cost;
};
void dijkstra(const vector<vector<Edge>> &G, int s, vector<long long> &dis) {
int N = G.size();
dis.resize(N, INF);
priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> pq; // ,
dis[s] = 0;
pq.emplace(dis[s], s);
while (!pq.empty()) {
pair<long long, int> p = pq.top();
pq.pop();
int v = p.second;
if (dis[v] < p.first) { //
continue;
}
for (auto &e : G[v]) {
if (dis[e.to] > dis[v] + e.cost) { // priority_queue
dis[e.to] = dis[v] + e.cost;
pq.emplace(dis[e.to], e.to);
}
}
}
}
//https://algo-logic.info/dijkstra/
//
void warshall_floyd(vector<vector<long long>> &dist) {
for (int k = 0; k < (int)dist.size(); k++) {
for (int i = 0; i < (int)dist.size(); i++) {
for (int j = 0; j < (int)dist.size(); j++) {
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
}
}
}
}
//https://qiita.com/okaryo/items/8e6cd73f8a676b7a5d75
//
// B-A
pair<long long,long long> bector(pair<long long,long long> A,pair<long long,long long> B){
return mp(B.first - A.first , B.second - A.second);
}
//(a,b)900
ll inner(pair<long long,long long> a,pair<long long,long long> b){
return a.first*b.first+a.second+b.second;
}
//(a,b)
ll outer(pair<long long,long long> a,pair<long long,long long> b){
return a.first*b.second-a.second*b.first;
}
long long merge_cnt(vector<long long> &a) {
long long n = a.size();
if (n <= 1) return 0;
long long cnt = 0;
vector<long long> b(a.begin(), a.begin()+n/2);
vector<long long> c(a.begin()+(n/2), a.end());
cnt += merge_cnt(b);
cnt += merge_cnt(c);
long long ai = 0, bi = 0, ci = 0;
while (ai < n) {
if ( bi < b.size() && (ci == c.size() || b[bi] <= c[ci]) ) {
a[ai++] = b[bi++];
} else {
cnt += n / 2 - bi;
a[ai++] = c[ci++];
}
}
return cnt;
}
/*UnionFindUnionFind uf() unite same size
!!
I am a cyan coder.
!!
*/
ll manhattan(pll A,pll B){
return(abs(A.fi-B.fi)+abs(A.se-B.se));
}
int main(){
ll N;
cin>>N;
vector<vector<ll>>rui(N,vector<ll>(2002,0));
vector<ll>A(N);
inV(A);
rui[0][A[0]]=1;
for(int i=1;i<N;i++){
for(int j=1;j<=2000;j++){
rui[i][j]=rui[i-1][j]+(A[i]==j);
}
}
ll Ans=0;
for(int i=1;i<N;i++){
for(int j=i+1;j<N-1;j++){
if(A[i]>A[j] && A[j]>10){
Ans+=rui[i-1][A[j]-10]*(rui[N-1][A[i]+1]-rui[j][A[i]+1]);
}
}
}
print(Ans);
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0