結果
| 問題 |
No.151 セグメントフィッシング
|
| コンテスト | |
| ユーザー |
 GOTKAKO
|
| 提出日時 | 2025-07-23 12:45:04 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 38 ms / 5,000 ms |
| コード長 | 7,595 bytes |
| コンパイル時間 | 2,037 ms |
| コンパイル使用メモリ | 206,220 KB |
| 実行使用メモリ | 7,716 KB |
| 最終ジャッジ日時 | 2025-07-23 12:45:08 |
| 合計ジャッジ時間 | 3,580 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 5 |
| other | AC * 19 |
ソースコード
#include <bits/stdc++.h>
using namespace std;
using SS = long long;
class SegmentTree{
public:
int siz = -1,n = -1;
vector<SS> dat;
SS op(SS a, SS b){return a+b;}
SS e(){return 0;}
void renew (SS &a,SS x){
a = op(a,x);
//a = x; //set(pos,x)で可能.
//その他.
}
SegmentTree(int N){init(N);}
SegmentTree(const vector<SS> &A){//長さ配列サイズに合わせる.
siz = 1; n = A.size();
while(siz < n) siz *= 2;
dat.resize(siz*2,e());
for(int i=0; i<n; i++) dat.at(i+siz) = A.at(i);
for(int i=siz-1; i>0; i--) dat.at(i) = op(dat.at(i*2),dat.at(i*2+1));
}
void init(int N){
//全要素単位元に初期化.
siz = 1; n = N;
while(siz < n) siz *= 2;
dat.assign(siz*2,e());
}
void init(const vector<SS> &A){//長さ配列サイズに合わせる.
siz = 1; n = A.size();
while(siz < n) siz *= 2;
dat.resize(siz*2,e());
for(int i=0; i<n; i++) dat.at(i+siz) = A.at(i);
for(int i=siz-1; i>0; i--) dat.at(i) = op(dat.at(i*2),dat.at(i*2+1));
}
void set(int pos,SS x){
pos = pos+siz;
dat.at(pos) = x;
while(pos != 1){
pos = pos/2;
dat.at(pos) = op(dat.at(pos*2),dat.at(pos*2+1));
}
}
void update(int pos,SS x){
pos = pos+siz;
renew(dat.at(pos),x);
while(pos != 1){
pos = pos/2;
dat.at(pos) = op(dat.at(pos*2),dat.at(pos*2+1));
}
}
SS findans(int l, int r){
SS retl = e(),retr = e();
l += siz,r += siz;
while(l < r){
if(l&1) retl = op(retl,dat.at(l++));
if(r&1) retr = op(dat.at(--r),retr);
l >>= 1; r >>= 1;
}
return op(retl,retr);
}
SS get(int pos){return dat.at(pos+siz);}
SS rangeans(int l, int r){return findans(l,r);}
SS allrange(){return dat.at(1);}
//rightは) leftは[で 渡す&返す.
int maxright(const function<bool(SS)> f,int l = 0){
//fを満たさない最小の箇所を返す なければn.
l += siz; int r = n+siz;
vector<int> ls,rs;
while(l < r){
if(l&1) ls.push_back(l++);
if(r&1) rs.push_back(--r);
l >>= 1; r >>= 1;
}
SS okl = e();
for(int i=0; i<ls.size(); i++){
l = ls.at(i);
SS now = op(okl,dat.at(l));
if(!f(now)){
while(l < siz){
l <<= 1;
now = op(okl,dat.at(l));
if(f(now)){okl = now; l++;}
}
return l-siz;
}
okl = now;
}
for(int i=rs.size()-1; i>=0; i--){
l = rs.at(i);
SS now = op(okl,dat.at(l));
if(!f(now)){
while(l < siz){
l <<= 1;
now = op(okl,dat.at(l));
if(f(now)){okl = now; l++;}
}
return l-siz;
}
okl = now;
}
return n;
}
int minleft(const function<bool(SS)> f,int r = -1){
//fを満たす最小の箇所を返す なければ0.
if(r == -1) r = n;
int l = siz; r += siz;
vector<int> ls,rs;
while(l < r){
if(l&1) ls.push_back(l++);
if(r&1) rs.push_back(--r);
l >>= 1; r >>= 1;
}
SS okr = e();
for(int i=0; i<rs.size(); i++){
r = rs.at(i);
SS now = op(dat.at(r),okr);
if(!f(now)){
while(r < siz){
r <<= 1; r++;
now = op(dat.at(r),okr);
if(f(now)){okr = now; r--;}
}
return r+1-siz;
}
okr = now;
}
for(int i=ls.size()-1; i>=0; i--){
r = ls.at(i);
SS now = op(dat.at(r),okr);
if(!f(now)){
while(r < siz){
r <<= 1; r++;
now = op(dat.at(r),okr);
if(f(now)){okr = now; r--;}
}
return r+1-siz;
}
okr = now;
}
return 0;
}
};
int main(){
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int N,Q; cin >> N >> Q;
SegmentTree R(N+1),L(N+1);
int time = 0;
auto moveLeft = [&](int l,int r) -> tuple<bool,int,bool,int> {
r--;
int back = 0;
bool Right = true;
while(back < time){
int move = min(l,time-back);
back += move,l -= move;
if(back != time) l = N,Right ^= 1;
}
back = 0;
bool Right2 = true;
while(back < time){
int move = min(r,time-back);
back += move,r -= move;
if(back != time) r = N,Right2 ^= 1;
}
return {Right,l,Right2,r};
};
auto moveRight = [&](int l,int r) -> tuple<bool,int,bool,int> {
r--; l = N-1-l,r = N-1-r; swap(l,r);
int back = 0;
bool Right = false;
while(back < time){
int move = min(l,time-back);
back += move,l -= move;
if(back != time) l = N,Right ^= 1;
}
back = 0;
bool Right2 = false;
while(back < time){
int move = min(r,time-back);
back += move,r -= move;
if(back != time) r = N,Right2 ^= 1;
}
return {Right,l,Right2,r};
};
bool end = false;
while(Q--){
char c = 'C';
if(end == false) cin >> c;
if(c == '-') end = true,c = 'C';
if(c == 'R'){
int x,v; cin >> x >> v;
bool Right = true;
int back = 0;
while(back < time){
int move = min(x,time-back);
back += move,x -= move;
if(back != time) x = N,Right ^= 1;
}
if(Right) R.update(x,v);
else L.update(x,v);
}
else if(c == 'L'){
int x,v; cin >> x >> v; x = N-1-x;
bool Left = true;
int back = 0;
while(back < time){
int move = min(x,time-back);
back += move,x -= move;
if(back != time) x = N,Left ^= 1;
}
if(Left) L.update(x,v);
else R.update(x,v);
}
else{
int l = 0,r = 1;
if(end == false) cin >> l >> r;
auto [Rl,l1,Rr,r1] = moveLeft(l,r);
long long answer = 0;
if(Rl == Rr){
r1++;
if(r1 == N) r1++;
if(Rl) answer += R.rangeans(l1,r1);
else answer += L.rangeans(l1,r1);
}
else{
if(Rl) answer += R.rangeans(l1,N+1)+L.rangeans(0,r1+1);
else answer += L.rangeans(l1,N+1)+R.rangeans(0,r1+1);
}
tie(Rl,l1,Rr,r1) = moveRight(l,r);
if(Rl == Rr){
r1++;
if(r1 == N) r1++;
if(Rl) answer += R.rangeans(l1,r1);
else answer += L.rangeans(l1,r1);
}
else{
if(Rl) answer += R.rangeans(l1,N+1)+L.rangeans(0,r1+1);
else answer += L.rangeans(l1,N+1)+R.rangeans(0,r1+1);
}
cout << answer << endl;
}
time++;
if(time == N+N) time = 0;
}
}