結果
問題 | No.674 n連勤 |
ユーザー | ゆにぽけ |
提出日時 | 2024-01-03 16:07:14 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 41 ms / 2,000 ms |
コード長 | 4,850 bytes |
コンパイル時間 | 1,360 ms |
コンパイル使用メモリ | 143,780 KB |
実行使用メモリ | 10,508 KB |
最終ジャッジ日時 | 2024-09-27 18:26:57 |
合計ジャッジ時間 | 2,398 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
6,816 KB |
testcase_01 | AC | 2 ms
6,944 KB |
testcase_02 | AC | 2 ms
6,940 KB |
testcase_03 | AC | 2 ms
6,940 KB |
testcase_04 | AC | 1 ms
6,940 KB |
testcase_05 | AC | 2 ms
6,940 KB |
testcase_06 | AC | 2 ms
6,944 KB |
testcase_07 | AC | 2 ms
6,940 KB |
testcase_08 | AC | 1 ms
6,944 KB |
testcase_09 | AC | 2 ms
6,940 KB |
testcase_10 | AC | 1 ms
6,944 KB |
testcase_11 | AC | 5 ms
6,940 KB |
testcase_12 | AC | 5 ms
6,944 KB |
testcase_13 | AC | 12 ms
6,940 KB |
testcase_14 | AC | 29 ms
10,508 KB |
testcase_15 | AC | 30 ms
10,044 KB |
testcase_16 | AC | 39 ms
10,484 KB |
testcase_17 | AC | 38 ms
10,344 KB |
testcase_18 | AC | 34 ms
9,912 KB |
testcase_19 | AC | 41 ms
10,352 KB |
ソースコード
#include <iostream> #include <string> #include <vector> #include <algorithm> #include <array> #include <cctype> #include <cstring> #include <cstdlib> #include <cassert> #include <cmath> #include <ctime> #include <iomanip> #include <numeric> #include <stack> #include <queue> #include <map> #include <unordered_map> #include <set> #include <unordered_set> #include <bitset> #include <random> #include <utility> #include <functional> using namespace std; template<class T,T (*op)(T,T),T e(),class F,T (*mapping)(F,T),F (*composition)(F,F),F id()> struct LazySegmentTree { private: vector<T> node; vector<F> lazy; int siz,log; void map_and_comp(F f,int u) { node[u] = mapping(f,node[u]); if(u < siz) lazy[u] = composition(f,lazy[u]); } void propagate(int u) { assert(0 <= u && u < siz); map_and_comp(lazy[u],2*u); map_and_comp(lazy[u],2*u+1); lazy[u] = id(); } void recalculate(int u) {node[u] = op(node[2*u],node[2*u+1]);} public: LazySegmentTree(int n = 0) : LazySegmentTree(vector<T>(n,e())) {} LazySegmentTree(const vector<T> &V) { siz = 1; log = 0; while(siz < (int)V.size()) siz <<= 1,log++; node.assign(2*siz,e()); lazy.assign(siz,id()); for(int i = 0;i < (int)V.size();i++) node[i+siz] = V[i]; for(int i = siz-1;i >= 1;i--) recalculate(i); } void fill(T x,int l = 0,int r = -1) {if(r < 0){r = siz;} for(int i = l;i < r;i++) replace(i,x);} void clear() {fill(e());} void replace(int pos,T x) {func_update(pos,x,[](T u,T v){return u = v;});} void add(int pos,T x) {func_update(pos,x,[](T u,T v){return u + v;});} void func_update(int pos,T x,T (*func)(T,T)) { assert(0 <= pos && pos < siz); pos += siz; for(int i = log;i >= 1;i--) propagate(pos >> i); node[pos] = func(node[pos],x); for(int i = 1;i <= log;i++) recalculate(pos >> i); } T operator[](int pos) { assert(0 <= pos && pos < siz); pos += siz; for(int i = log;i >= 1;i--) propagate(pos >> i); return node[pos]; } void apply(int pos,F f) { assert(0 <= pos && pos < siz); pos += siz; for(int i = log;i >= 1;i--) propagate(pos >> i); node[pos] = mapping(f,node[pos]); for(int i = 1;i <= log;i++) recalculate(pos >> i); } void apply(int l,int r,F f) { assert(0 <= l && l <= r && r <= siz); if(l == r) return; l += siz; r += siz; int l0 = l/(l & -l); int r0 = r/(r & -r); for(int i = log;i >= 1;i--) propagate(l0 >> i); for(int i = log;i >= 1;i--) propagate((r0-1) >> i); while(l < r) { if(l & 1) map_and_comp(f,l++); if(r & 1) map_and_comp(f,--r); l >>= 1; r >>= 1; } for(int i = 1;i <= log;i++) recalculate(l0 >> i); for(int i = 1;i <= log;i++) recalculate((r0-1) >> i); } T prod() {return node[1];} T prod(int l,int r) { assert(0 <= l && l <= r && r <= siz); l += siz; r += siz; int l0 = l/(l & -l); int r0 = r/(r & -r); for(int i = log;i >= 1;i--) propagate(l0 >> i); for(int i = log;i >= 1;i--) propagate((r0-1) >> i); T Lval = e(),Rval = e(); while(l < r) { if(l & 1) Lval = op(Lval,node[l++]); if(r & 1) Rval = op(node[--r],Rval); l >>= 1; r >>= 1; } return op(Lval,Rval); } }; struct S { long long l,r,size,mx; }; S op(S a,S b) { S x; x.l = a.l; if(a.l == a.size) x.l += b.l; x.r = b.r; if(b.r == b.size) x.r += a.r; x.mx = max(a.mx,b.mx); x.mx = max(x.mx,a.r + b.l); x.size = a.size + b.size; return x; } S e() { return S{0,0,0,0}; } S mp(int f,S x) { if(f) { x.l = x.size; x.r = x.size; x.mx = x.size; } return x; } int cp(int f,int g) { return f|g; } int id() { return 0; } void solve() { long long D; int Q; cin >> D >> Q; vector<long long> comp; vector<long long> A(Q),B(Q); for(int i = 0;i < Q;i++) { cin >> A[i] >> B[i]; comp.push_back(A[i]); comp.push_back(++B[i]); } sort(comp.begin(),comp.end()); comp.erase(unique(comp.begin(),comp.end()),comp.end()); vector<S> init(comp.size() - 1); for(int i = 0;i + 1 < (int)comp.size();i++) { init[i].size = comp[i+1] - comp[i]; } LazySegmentTree<S,op,e,int,mp,cp,id> seg(init); for(int i = 0;i < Q;i++) { int l = lower_bound(comp.begin(),comp.end(),A[i]) - comp.begin(); int r = lower_bound(comp.begin(),comp.end(),B[i]) - comp.begin(); seg.apply(l,r,1); cout << seg.prod().mx << "\n"; } } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int tt = 1; /* cin >> tt; */ while(tt--) solve(); }