結果

問題 No.1708 Quality of Contest
ユーザー aiueokaaiueoka
提出日時 2021-11-08 16:06:15
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 374 ms / 2,000 ms
コード長 5,220 bytes
コンパイル時間 4,763 ms
コンパイル使用メモリ 243,800 KB
実行使用メモリ 27,220 KB
最終ジャッジ日時 2024-11-16 10:38:15
合計ジャッジ時間 13,035 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 3 ms
5,248 KB
testcase_02 AC 3 ms
5,248 KB
testcase_03 AC 7 ms
5,248 KB
testcase_04 AC 8 ms
5,248 KB
testcase_05 AC 8 ms
5,248 KB
testcase_06 AC 6 ms
5,248 KB
testcase_07 AC 12 ms
5,248 KB
testcase_08 AC 3 ms
5,248 KB
testcase_09 AC 318 ms
27,220 KB
testcase_10 AC 262 ms
23,000 KB
testcase_11 AC 332 ms
20,816 KB
testcase_12 AC 353 ms
21,676 KB
testcase_13 AC 333 ms
20,028 KB
testcase_14 AC 359 ms
22,060 KB
testcase_15 AC 367 ms
25,168 KB
testcase_16 AC 367 ms
24,804 KB
testcase_17 AC 356 ms
22,528 KB
testcase_18 AC 354 ms
22,820 KB
testcase_19 AC 356 ms
23,664 KB
testcase_20 AC 351 ms
22,416 KB
testcase_21 AC 366 ms
22,984 KB
testcase_22 AC 362 ms
22,112 KB
testcase_23 AC 374 ms
25,012 KB
testcase_24 AC 282 ms
18,648 KB
testcase_25 AC 281 ms
18,648 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
#include<atcoder/all>
using namespace std;
using namespace atcoder;
using ll=long long;
using ld=long double;
using vvi=vector<vector<int>>;
using vi=vector<int>;
using vpi=vector<pair<int,int>>;
using vvl=vector<vector<ll>>;
using vl=vector<ll>;
using vpl=vector<pair<ll,ll>>;
using vb=vector<bool>;
using vvb=vector<vb>;
using mint=modint1000000007;
using mint9=modint998244353;
using P=pair<ll,ll>;
using Pi=pair<int,int>;
#define outs cout << " ";
#define outl cout << endl;
ll mod1=1000000007,mod2=998244353;
ll intmax=2147483647,llmax=9223372036854775807;
#define rep(i, s, n) for (ll i = s; i < (ll)(n); i++)
#define dep(i, s, n) for (ll i = n-1; i >=(ll)(s); i--)
#define rem(i, s, n, t) for(ll i = s; i < (ll)(n); t, i++) 
#define dem(i, s, n, t) for(ll i = n-1; i >=(ll)(s); t, i--)
#define all(a) (a).begin(),(a).end()
#define allr(a) (a).rbegin(),(a).rend()
#define nr cout << "No" << endl;return 0;
#define print(a) cout << a << " ";
#define np next_permutation
#define fi first
#define se second
#define sor(a) sort(all(a))
#define sorr(a) sort(allr(a))
#define grl greater<ll>
#define gri greater<int>
#define sizel(a) ll(a.size())
#define pb push_back
#define alout(a) {rep(i,0,a.size())cout << a[i] << " ";outl;}
#define chmax(a,b) a=max(a,b);
#define chmin(a,b) a=min(a,b);
void fix(ll a){cout << fixed << setprecision(a);}
void yn(bool a){if(a){cout<<"Yes"<<endl;}else{cout<<"No"<<endl;}}
void alllut(vi s){rep(i,0,s.size())cout << s[i] << " ";outl;}
void allout(vl s){
  rep(i,0,s.size()-1)cout << s[i] << " ";
  cout << s[s.size()-1] << endl;
}
void ifout(bool a,ll x,ll y){cout << ((a)?x:y);}
void paut(pair<ll,ll> s){cout << s.fi << " " << s.se << endl;}
void pout(pair<ll,ll> s){cout << s.fi << " " << s.se << endl;}
ll keta(ll i,ll j){i=i%ll(pow(10,j))/ll(pow(10,j-1));return i;}// j = 0 は ダメ
ll pm1(ll x,ll y){ll s=1;for(ll i=0;i<y;i++)s=s*x%mod1;return s;}
ll pm2(ll x,ll y){ll s=1;for(ll i=0;i<y;i++)s=s*x%mod2;return s;}
mint cnvm(ll x,ll y){if(x<y)return 0;mint s=1;rep(i,1,y+1){s=s*(x+1-i)/i;}return s;}
mint9 cnvm9(ll x,ll y){if(x<y)return 0;mint9 s=1;rep(i,1,y+1){s=s*(x+1-i)/i;}return s;}
ll cnv(ll x,ll y){if(x<y)return 0;ll s=1;rep(i,1,y+1){s=s*(x+1-i)/i;}return s;}
ll gcd(ll a,ll b){for(;min(a,b)>0;)if(a<b)b%=a;else a%=b;return max(a,b);}
ll lcm(ll a,ll b){return a/gcd(a,b)*b;}
string tak="Takahashi",aok="Aoki",yes="Yes",no="No",fir="First",sec="Second";
ll kosuu(ll a,ll b){return max(ll(0),b-a+1);}
ll modpow(ll a,ll b,ll mod=llmax){
  ll ans=1;
  while(b){
    if(b%2==1)ans=ans*a%mod;
    a=a*a%mod;
    b/=2;
  }
  return ans;
}
void asdf(){cout << "?" << endl;}
/*
ll l=0,r=a.size();
while(l+1<r){
  ll w=(l+r)/2;
  if(w<(=:tarを含むとき)tar)
  else
}
*/
// '0'=48, 'A'=65, 'Z'=90, 'a'=97', 'z'=122
string tolower(string s){
  rep(i,0,s.size())if(s[i]<91)s[i]=s[i]+32;
  return s;
}
string toupper(string s){
  rep(i,0,s.size())if(s[i]>96)s[i]=s[i]-32;
  return s;
}
ll MAX,mod=mod1;
vl fac,finv,inv;
void COMinit(){
  MAX++;
  fac.resize(MAX);
  finv.resize(MAX);
  inv.resize(MAX);
  fac[0]=fac[1]=1;
  finv[0]=finv[1]=1;
  inv[1]=1;
  rep(i,2,MAX){
    fac[i]=fac[i-1]*i%mod;
    inv[i]=mod-inv[mod%i]*(mod/i)%mod;
    finv[i]=finv[i-1]*inv[i]%mod;
  }
}
ll com(ll n,ll k){
  if(n<k)return 0;
  if(n<0||k<0)return 0;
  return fac[n]*(finv[k]*finv[n-k]%mod)%mod;
}
ll MAx;
vl fact;
void FACT(){
  fact=vl(MAx+1,1);
  rep(i,1,MAx+1)fact[i]=fact[i-1]*i;
}
ll upper(vl a,ll b){
  //if(a[0]>b)
  ll l=0,r=a.size()-1;
  while(l+1<r){
    ll w=(l+r)/2;
    if(a[w]<=b)l=w;
    else r=w;
  }
  return l+1;
}
ll lower(vl a,ll b){
  ll l=0,r=a.size()-1;
  while(l+1<r){
    ll w=(l+r)/2;
    if(a[w]<b)l=w;
    else r=w;
  }
  return l+1;
}

ll dai(ll n){
  vi s;
  while(n){
    s.push_back(n%10);
    n/=10;
  }
  sort(all(s));
  for(int i=s.size()-1;i>-1;i--){
    n+=s[i]*pow(10,i);
  }
  return n;
}
ll syou(ll n){
  vi s;
  while(n){
    s.push_back(n%10);
    n/=10;
  }
  sort(all(s));
  rep(i,0,s.size()){
    n+=s[i]*pow(10,s.size()-i-1);
  }
  return n;
}
ll yakusuu(ll a){
  ll co=0;
  for(ll i=1;i*i<a;i++)if(a%i==0)co+=2;
  if(a==pow((int)sqrt(a),2))co++;
  return co;
}
void pin(P &a){
  cin>>a.fi>>a.se;
}
bool prime(ll a){
  rep(i,2,sqrt(a)+1)if(a%i==0)return 0;
  return 1;
}
ll LIS(vl a){
  vl ret;
  for(ll u:a){
    auto itr=lower_bound(all(ret),u);
    if(itr!=ret.end())*itr=u;
    else ret.push_back(u);
  }
  return ll(ret.size());
}
// priority_queue<ll,vl,grl> greater
ll sl=1,ls=0,inf=1e18;

// segtree l~r-1

P f(P a,P b){
  return make_pair(max(a.fi,b.fi),(a.fi>=b.fi?a.se:b.se));
  //return ret;
}
P s(){
  return make_pair(ls,ls);
  //return ret;
}

int main(){
  ll n,m,x;cin>>n>>m>>x;
  vl b(n),a(n);vvl to(m);
  segtree<P,f,s> seg(n);
  rep(i,0,n){
    cin>>a[i]>>b[i];b[i]--;
    to[b[i]].pb(i);
    seg.set(i,make_pair(a[i]+x,i));
  }
  vl as(n);vb seen(m);
  rep(i,0,n){
    P v=seg.all_prod();
    as[i]=(i==0?0:as[i-1])+v.fi;
    seg.set(v.se,make_pair(ls,v.se));
    if(seen[b[v.se]]==0){
      for(ll u:to[b[v.se]])seg.set(u,make_pair(seg.get(u).fi-x,u));
      seen[b[v.se]]=1;
    }
  }
  ll k;cin>>k;
  ll ans=0;
  rep(i,0,k){
    ll c;cin>>c;c--;
    ans+=(c<0?0:as[c]);
  }
  cout << ans << endl;
}
0