結果
問題 | No.1708 Quality of Contest |
ユーザー | aiueoka |
提出日時 | 2021-11-08 16:06:15 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.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 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 23 |
ソースコード
#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'=122string 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> greaterll sl=1,ls=0,inf=1e18;// segtree l~r-1P 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;}