結果

問題 No.3197 Frequency Counter
ユーザー eiram
提出日時 2025-07-11 21:42:36
言語 C++17(gcc12)
(gcc 12.3.0 + boost 1.87.0)
結果
AC  
実行時間 721 ms / 2,000 ms
コード長 8,008 bytes
コンパイル時間 20,055 ms
コンパイル使用メモリ 302,928 KB
実行使用メモリ 23,552 KB
最終ジャッジ日時 2025-07-11 21:43:04
合計ジャッジ時間 24,958 ms
ジャッジサーバーID
(参考情報)
judge2 / judge3
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
other AC * 21
権限があれば一括ダウンロードができます

ソースコード

diff #

#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;
using namespace atcoder;

#define INF 1LL<<60
#define MOD 998244353
#define MMOD 1000000007
using mint=modint998244353;

using ll=long long;
using ull=unsigned long long;
using ld=long double;
template<typename T> using vc=vector<T>;
template<typename T> using vv=vc<vc<T>>;
using vl=vector<ll>;
using vvl=vv<ll>;
using vs=vc<string>;
using vvs=vv<string>;
using vb=vc<bool>;
using vvb=vv<bool>;
using lP=pair<ll,ll>;
using vlp=vc<lP>;

template<typename T> bool chmin(T& a, T b){if(a > b){a = b; return true;} return false;}
template<typename T> bool chmax(T& a, T b){if(a < b){a = b; return true;} return false;}

#define YES cout<<"Yes"<<endl
#define NO cout<<"No"<<endl
#define YN {cout<<"Yes"<<endl;}else{cout<<"No"<<endl;}
struct Edge {
    ll to;
    ll weight;
    Edge(ll t, ll w) : to(t), weight(w) { }
};
using Graph=vector<vector<Edge>>;

vl dx={0,0,1,-1};
vl dy={1,-1,0,0};

vector<ll> dijkstra(Graph &G,ll s){
    vl dist(ll(G.size()),INF);
    priority_queue<pair<ll,ll>,vector<lP>,greater<lP>> pq;
    dist[s]=0;
    pq.push({0,s});
    while(!pq.empty()){
        lP p=pq.top();
        ll d=p.first;
        ll v=p.second;
        pq.pop();
        if(d>dist[v]) continue;
        for(auto &e:G[v]){
            if(d+e.weight<dist[e.to]){
                dist[e.to]=d+e.weight;
                pq.push({dist[e.to],e.to});
            }
        }
    }
    return dist;
}

bool outgrid(ll y,ll x,ll h,ll w){
    return (y>=h||x>=w||y<0||x<0);
};

//Gにグラフ、sがスタート地点。sからの距離が返り値の配列に入る。
vl bfs(vvl &G,ll s){
    vl dist(G.size(),INF);
    queue<ll> q;
    dist[s]=0;
    q.push(s);
    while(!q.empty()){
        ll v=q.front();
        q.pop();
        for(auto &e:G[v]){
            if(dist[e] != INF) continue;
            dist[e]=dist[v]+1;
            q.push(e);
        }
    }
    return dist;
};

//壁がある時にcontinueするならコメントアウト外して!
vvl gridbfs(vs &G,ll sy,ll sx){
    vvl dist(G.size(),vl(G[0].size(),INF));
    queue<lP> q;
    dist[sy][sx]=0;
    q.push(make_pair(sy,sx));
    while(!q.empty()){
        lP p=q.front();
        ll y=p.first;
        ll x=p.second;
        q.pop();
        for(int i=0;i<4;i++){
            ll ny=y+dy[i];
            ll nx=x+dx[i];
            if(outgrid(ny,nx,G.size(),G[0].size())) continue;
            if(dist[ny][nx]!=INF) continue;
            // if(g[ny][nx]=='#') continue;
            dist[ny][nx]=dist[y][x]+1;
            q.push(make_pair(ny,nx));
        }
    }
    return dist;
}

vb vi;
//Gにグラフ、nowが今の場所。この分の上にvisited書いてね。main内でviをresizeもしてね。
void dfs(vvl &G,ll now){
    vi[now]=true;
    for(auto &e:G[now]){
        if(vi[e]) continue;
        dfs(G,e);
    }
};

ll pathcnt=0;
//n頂点全てを通るパスが何通りあるかをpathcntに記憶する。上にn宣言、main内でviをresizeしてね。cntは最初は1。コメントアウト外してね。
void pathdfs(vvl &G,ll now,ll cnt){
    vi[now]=true;
    //if(cnt==n) pathcnt++;
    for(auto &e:G[now]){
        if(vi[e]) continue;
        pathdfs(G,e,cnt+1);
    }
    vi[now]=false;
}

vv<bool> visi;
ll h,w;
//グリッド上DFS。探索して行けるとこはvisiがtrue,行けないとこはfalse。visiとh,wを上に!main内でresizeも!
void on_the_grid_dfs(vs &G,ll y,ll x){
    visi[y][x]=true;
    for(int i=0;i<4;i++){
        ll nx=x+dx[i];
        ll ny=y+dy[i];
        if(outgrid(ny,nx,h,w)) continue;
        if(visi[ny][nx]) continue;
        on_the_grid_dfs(G,ny,nx);
    }
};

struct unionfind{
    vl par,rank,siz; //par(x)=要素xの親頂点の番号(自身が根の場合は-1
                     //rank(x)=要素xの属する根付き木の高さ
                     //siz(x)=要素xの属する根付き木に含まれる超点数
    unionfind(int n) :par(n,-1),rank(n,0),siz(n,1) { }

    ll root(ll x){
        if(par[x]==-1) return x;
        else return par[x]=root(par[x]);
    }
    bool issame(ll x,ll y){
        return root(x)==root(y);
    }
    void unite(ll x,ll y){
        x=root(x);
        y=root(y);
        if(x==y) return ;
        if(rank[x]<rank[y]){
            par[x]=y;
            siz[y]+=siz[x];
        }else{
            par[y]=x;
            siz[x]+=siz[y];
            if(rank[x]==rank[y]) ++rank[x];
        }
    }
    bool same(ll x,ll y){
        return root(x)==root(y);
    }
    ll size(ll x){
        return siz[root(x)];
    }
    ll countsets(){
        ll cnt=0;
        for(ll i=0;i<ll(par.size()); ++i) if(par[i]==i)++cnt;
        return cnt;
    }
};

vector<pair<char,ll>> RLE(string s){
    vector<pair<char,ll>> rle;
    for(char c:s){
        if(rle.empty() || rle.back().first != c) rle.emplace_back(c,1);
        else rle.back().second++;
    }
    return rle;
};
//2進数から10進数へ
ll base2to10(string s){
    ll n=s.size();
    ll ans=0;
    ll a=1;
    reverse(s.begin(),s.end());
    for(int i=0;i<n;i++){
        if(s[i]=='1') ans+=a;
        a*=2;
    }
    return ans;
};
//x進数から10進数へ
ll basexto10(string s,ll x){
    ll n=s.size();
    ll ans=0;
    ll a=1;
    reverse(s.begin(),s.end());
    for(int i=0;i<n;i++){
        if(s[i]!='0') ans+=a*(char(s[i]-'0'));
        a*=x;
    }
    return ans;
}

//10進数からx進数へ2<=x<=16(返り値は文字列型なので注意。)
string base10tox(ll n,ll x){
    string ans="";
    ll a=1;
    vc<char> digits={'0','1','2','3','4','5','6','7','8','9','A','B','C','D','E','F'};
    do{
        ans+=digits[n%x];
        n/=x;
    }while(n);
    reverse(ans.begin(),ans.end());
    return ans;
};

ld manhattan(ld x,ld y,ld x2,ld y2){
    return (abs(x-x2)+abs(y-y2));
};

ll gcd(ll a,ll b){
    while(a>=1&&b>=1){
        if(a<b) b=b%a;
        else a=a%b;
    }
    if(a>=1) return a;
    return b;
}

//nを素因数分解して、pairで(素数,指数)が返される。
vlp pfact(ll n){
    vlp a;
    for(ll i=2;i*i<=n;i++){
        if(n%i!=0) continue;
        ll ex=0;
        while(n%i==0){
            ex++;
            n/=i;
        }
        a.emplace_back(i,ex);
    }
    if(n!=1) a.emplace_back(n,1);
    return a;
}
//nを素因数分解して、配列で素数が返される。(総積がnになる)
vl pfact2(ll n){
    vl a;
    for(ll i=2;i*i<=n;i++){
        while(n%i==0){
            n/=i;
            a.push_back(i);
        }
    }
    if(n!=1) a.push_back(n);
    return a;
}

//n以下の整数について素数判定をしてnまでの素数が昇順に入ってる配列を返す。
vl eratosthenes(ll n){ 
    vb isprime(n,false);
    vl p;
    for(int i=2;i<n;i++){
        if(isprime[i]) continue;
        p.push_back(i);
        for(int j=i;j<n;j+=i) isprime[j]=true;
    }
    return p;
}

//時計回りに配列を回転させるa=rotate(a)って感じで使う。
vvl rotate(vvl a){
    vvl b(a.size(),vl(a[0].size()));
    for(int i=1;i<=a.size();i++){
        for(int j=1;j<=a[0].size();j++){
            b[i-1][j-1]=a[(a.size()+1-j)-1][i-1];
        }
    }
    return b;
}

//時計回りに文字列配列を回転させるa=rotate(a)って感じで使う。
vs string_rotate(vs a){
    vs b(a.size(),string(a.size(),'*'));
    for(int i=1;i<=a.size();i++){
        for(int j=1;j<=a.size();j++){
            b[i-1][j-1]=a[(a.size()+1-j)-1][i-1];
        }
    }
    return b;
}

//2つのグリッドで何箇所違う文字のところがあるか探索する。
ll differentcount(vs s,vs t){
    ll h=s.size(),w=s[0].size();
    ll cnt=0;
    for(int i=0;i<h;i++){
        for(int j=0;j<w;j++){
            if(s[i][j]!=t[i][j]) cnt++;
        }
    }
    return cnt;
}

int main() {
    ll n;
    cin>>n;
    map<ll,ll> ma;
    vl a(n);
    for(int i=0;i<n;i++) {
        cin>>a[i];
        ma[a[i]]++;
    }
    ll q;
    cin>>q;
    for(int i=0;i<q;i++){
        ll x,k;
        cin>>x>>k;
        if(ma[x]>=k) YN;
    }
    
}
0