codeFlyer （bitFlyer Programming Contest）E - 祝日

実装力。大事。

問題

E - 祝日

感想

これは正直やるだけですよね。

インプットの状態での祝日を数えた後、一つずつ曜日をずらしていって日数がどう変わるかを見ていきます。

日にちの管理はsetで行い、抜き差しする際に祝日の計算をします。

一年の開始の曜日がずれるのは、全体が一日ずれたとみるとＡの方の処理も簡単です。該当するＢのほうは＋ｗ。

これが書ければ終わりです。しかしこれが書けない。

ということで赤い方のコードを参考にさせてもらいましたが、いやー、これがすごい。無駄が全然見当たらないんですよこれが。

setでものを管理するとき、両端は何か入れとくのは基本ですね。
祝日がぶつからないようにPairで持っているのも賢い。

これが実装力なんだなあ、という気持ちになりました。

コード

#include <bits/stdc++.h>

using namespace std;

#ifdef DEBUG_MODE
	#define DBG(n) n;
#else
	#define DBG(n) ;
#endif
#define REP(i,n) for(ll (i) = (0);(i) < (n);++i)
#define rep(i,s,g) for(ll (i) = (s);(i) < (g);++i)
#define rrep(i,s,g) for(ll (i) = (s);i >= (g);--(i))
#define PB push_back
#define MP make_pair
#define FI first
#define SE second
#define SHOW1d(v,n) {for(int WWW = 0;WWW < (n);WWW++)cerr << v[WWW] << ' ';cerr << endl << endl;}
#define SHOW2d(v,i,j) {for(int aaa = 0;aaa < i;aaa++){for(int bbb = 0;bbb < j;bbb++)cerr << v[aaa][bbb] << ' ';cerr << endl;}cerr << endl;}
#define ALL(v) v.begin(),v.end()
#define Decimal fixed<<setprecision(20)
#define INF 1000000000
#define LLINF 100000000000000000LL
#define MOD 1000000007

typedef long long ll;
typedef pair<ll,ll> P;

ll y,w,n,m,d,ans;
set<pair<ll,int>> s;

ll check(ll l,ll r){
	if(l == r)return 0;
	if(r - l - 1 <= d)return r - l;
	return 1;
}

void m_insert(ll x,int flag){
	auto it = s.upper_bound(MP(x,flag));
	ll now_r = it -> FI;
	it--;
	ll now_l = it -> FI;
	ans -= check(now_l,now_r);
	ans += check(now_l,x) + check(x,now_r);
	s.insert(MP(x,flag));
}

void m_erase(ll x,int flag){
	auto it = s.lower_bound(MP(x,flag));
	it++;
	ll now_r = it -> FI;
	it--;it--;
	ll now_l = it -> FI;
	it++;
	ans += check(now_l,now_r);
	ans -= check(now_l,x) + check(x,now_r);
	s.erase(it);
}

int main(){
	
	cin >> y >> w >> n >> m >> d;
	s.insert(MP(LLINF,false));
	s.insert(MP(-LLINF,false));
	
	DBG(cout << "ans : " << ans << endl;)
	
	vector<ll> A(n);
	REP(i,n){
		cin >> A[i];A[i]--;
		m_insert(A[i],i);
	}
	
	vector<vector<ll>> B(w+1);
	REP(i,m){
		ll b,c;cin >> b >> c;b--;c--;
		B[c].PB(b);
		m_insert(w*b+c,n+(B[c].size()-1));
	}
	
	DBG(cout << "ans : " << ans << endl;)
	
	REP(i,w){
		cout << ans << endl;
		
		REP(j,n){
			m_erase(A[j],j);
			A[j]++;
			m_insert(A[j],j);
		}
		
		REP(j,B[i].size()){
			m_erase(i+w*B[i][j],n+j);
			m_insert(i+w*(B[i][j]+1),n+j);
		}
	}

	return 0;
}