結果
問題 |
No.230 Splarraay スプラレェーイ
|
ユーザー |
![]() |
提出日時 | 2019-05-28 13:36:48 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 174 ms / 5,000 ms |
コード長 | 2,266 bytes |
コンパイル時間 | 949 ms |
コンパイル使用メモリ | 105,556 KB |
実行使用メモリ | 11,392 KB |
最終ジャッジ日時 | 2024-09-17 15:39:07 |
合計ジャッジ時間 | 3,669 ms |
ジャッジサーバーID (参考情報) |
judge6 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 17 |
ソースコード
#include <cstdio> #include <cstring> #include <iostream> #include <string> #include <cmath> #include <bitset> #include <vector> #include <map> #include <set> #include <queue> #include <deque> #include <algorithm> #include <complex> #include <unordered_map> #include <unordered_set> #include <random> #include <cassert> #include <fstream> #define popcount __builtin_popcount using namespace std; typedef long long ll; typedef pair<int, int> P; const ll INF=1e9; struct RSQandRUQ{ vector<ll> sum, part; int n, m; RSQandRUQ(int size):n(size){ m=1; while(m<n) m<<=1; sum.resize(2*m); part.resize(2*m); } void eval(int k, int l, int r){ if(part[k]<INF){ sum[k]=part[k]*(ll)(r-l); if(k<m-1){ part[2*k+1]=part[k]; part[2*k+2]=part[k]; } part[k]=INF; } } void update(int a, int b, ll x, int k, int l, int r){ eval(k, l, r); if(r<=a || b<=l) return; if(a<=l && r<=b){ part[k]=x; eval(k, l, r); }else{ update(a, b, x, 2*k+1, l, (l+r)/2); update(a, b, x, 2*k+2, (l+r)/2, r); sum[k]=sum[2*k+1]+sum[2*k+2]; } } ll getsum(int a, int b, int k, int l, int r){ eval(k, l, r); if(b<=l || r<=a) return 0; if(a<=l && r<=b) return sum[k]; else return getsum(a, b, 2*k+1, l, (l+r)/2)+getsum(a, b, 2*k+2, (l+r)/2, r); } void update(int a, int b, ll x){ update(a, b, x, 0, 0, m); } ll getsum(int a, int b){ return getsum(a, b, 0, 0, m); } }; int main() { int n, q; cin>>n>>q; RSQandRUQ a(n), b(n); ll ansa=0, ansb=0; for(int i=0; i<q; i++){ int x, l, r; cin>>x>>l>>r; if(x==0){ ll s=b.getsum(l, r+1), t=a.getsum(l, r+1); if(s>0) ansa+=(s+t)/2; else if(s<0) ansb+=(t-s)/2; }else if(x==1){ a.update(l, r+1, 1); b.update(l, r+1, 1); }else{ a.update(l, r+1, 1); b.update(l, r+1, -1); } } ll s=b.getsum(0, n), t=a.getsum(0, n); ansa+=(s+t)/2; ansb+=(t-s)/2; cout<<ansa<<" "<<ansb<<endl; return 0; }