AOJ 0536 JOI 予選過去問 シャッフル
進捗アリです。
めんどくさかった
予選でフィードバックないから死んじゃう
解法はjoi公式の奴と一緒です。
はい。
ちょっとおんなじことを繰り返している部分があるけど直すのめんどいんですいませぇん
//こんな問題予選に出たら解きたくないわ~ #include <cstdio> #include <deque> using namespace std; int main(){ while(1){ int n,m,p,q,r; deque<pair<int,int> > d; scanf("%d",&n); if(n == 0) break; scanf("%d%d%d%d",&m,&p,&q,&r); d.push_back(make_pair(1,n)); for(int i = 0;i < m;i++){ int x,y,g = 0; scanf("%d%d",&x,&y); deque<pair<int,int> > a,b; while(1){ pair<int,int> nau = d.front(); d.pop_front(); g += nau.second - nau.first + 1; if(g == x){ a.push_back(nau); break; }else if(g < x){ a.push_back(nau); }else{ a.push_back(make_pair(nau.first,nau.second-(g-x))); d.push_front(make_pair(nau.second-(g-x)+1,nau.second)); break; } } g = x; while(1){ pair<int,int> nau = d.front(); d.pop_front(); g += nau.second - nau.first + 1; if(g == y){ b.push_back(nau); break; }else if(g < y){ b.push_back(nau); }else{ b.push_back(make_pair(nau.first,nau.second-(g-y))); d.push_front(make_pair(nau.second-(g-y)+1,nau.second)); break; } } for(int i = 0;i < b.size();i++) d.push_back(b[i]); for(int i = 0;i < a.size();i++) d.push_back(a[i]); } int g = 0,pre = 0; int ans = 0; while(1){ if(pre > q || d.empty()) break; pair<int,int> nau = d.front(); d.pop_front(); g += nau.second - nau.first + 1; if(g < p){ pre = g + 1; continue; } int st=nau.first,fi=nau.second; if(pre < p) st += p - pre; if(g > q) fi -= (g - q); pre = g + 1; if(st > r)continue; if(fi <= r){ ans += fi - st + 1; }else{ ans += r - st + 1; } } printf("%d\n",ans); } return 0; }