結果

問題 No.833 かっこいい電車
ユーザー NyaanNyaanNyaanNyaan
提出日時 2019-05-24 22:41:26
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 161 ms / 2,000 ms
コード長 7,287 bytes
コンパイル時間 986 ms
コンパイル使用メモリ 104,140 KB
実行使用メモリ 14,376 KB
最終ジャッジ日時 2023-09-14 20:54:40
合計ジャッジ時間 4,627 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge11
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 124 ms
8,864 KB
testcase_01 AC 1 ms
4,380 KB
testcase_02 AC 2 ms
4,376 KB
testcase_03 AC 2 ms
4,376 KB
testcase_04 AC 1 ms
4,376 KB
testcase_05 AC 2 ms
4,376 KB
testcase_06 AC 2 ms
4,376 KB
testcase_07 AC 2 ms
4,376 KB
testcase_08 AC 2 ms
4,380 KB
testcase_09 AC 2 ms
4,376 KB
testcase_10 AC 115 ms
9,084 KB
testcase_11 AC 161 ms
12,836 KB
testcase_12 AC 48 ms
7,384 KB
testcase_13 AC 29 ms
4,556 KB
testcase_14 AC 136 ms
12,796 KB
testcase_15 AC 63 ms
8,640 KB
testcase_16 AC 55 ms
10,152 KB
testcase_17 AC 37 ms
4,376 KB
testcase_18 AC 141 ms
9,324 KB
testcase_19 AC 52 ms
9,432 KB
testcase_20 AC 14 ms
5,496 KB
testcase_21 AC 104 ms
6,244 KB
testcase_22 AC 94 ms
13,636 KB
testcase_23 AC 60 ms
9,696 KB
testcase_24 AC 92 ms
13,076 KB
testcase_25 AC 132 ms
8,620 KB
testcase_26 AC 65 ms
11,272 KB
testcase_27 AC 97 ms
9,092 KB
testcase_28 AC 63 ms
5,916 KB
testcase_29 AC 80 ms
8,008 KB
testcase_30 AC 108 ms
14,376 KB
testcase_31 AC 120 ms
9,072 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <algorithm>
#include <cassert>
#include <cmath>
#include <cstdarg>
#include <cstdio>
#include <cstring>
#include <deque>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <utility>
#include <vector>

#define whlie while
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define inf 1001001001
#define infLL ( (1LL << 61) - 10)
#define mod 1000000007
#define FOR(i,a,b) for(int (i)=((int)a); (i)<((int)b); (i)++) // [a,b)
#define rep(i,N) FOR((i), 0, ((int)N)) // [0,N)
#define FORR(i,a,b) for(int (i)=((int)b) - 1; (i)>=((int)a); (i)--)
#define repr(i,N) FORR((i), 0, ((int)N))
#define all(v) (v).begin(),(v).end()
#define sz(v) ((int)(v).size())
#define vrep(v,it) for(auto it=v.begin();it!=v.end();it++)
#define vrepr(v,it) for(auto it=v.rbegin();it!=v.rend();it++)
#define inx(t,...) t __VA_ARGS__; in(__VA_ARGS__)
#define ini(...) int __VA_ARGS__; in(__VA_ARGS__)
#define inl(...) ll __VA_ARGS__; in(__VA_ARGS__)
#define inc(...) char __VA_ARGS__; in(__VA_ARGS__)
#define ins(...) string __VA_ARGS__; in(__VA_ARGS__)
#define ind(...) double __VA_ARGS__; in(__VA_ARGS__)
#define inpii(...) pii __VA_ARGS__; in(__VA_ARGS__)
#define invi(v,...) vi v; in(v,##__VA_ARGS__)
#define invl(v,...) vl v; in(v,##__VA_ARGS__)
#define mem(ar,val) memset((ar), (val), sizeof(ar) )
#define mem0(ar) memset((ar),  0, sizeof(ar) )
#define mem1(ar) memset((ar), -1, sizeof(ar) )

#ifdef LOCAL
    #define dbg(...) fprintf(stderr, __VA_ARGS__)
    #define trc(...) do { cout << #__VA_ARGS__ << "="; dbg_out(__VA_ARGS__);} while(0)
    #define stopif(val) assert( !(val) )
    #define vdbg(v,...) do { cout << #v << " = "; vector_debug(v , ##__VA_ARGS__);} while(0)
#else
    #define dbg(...) 1
    #define trc(...) 1
    #define stopif(...) 1
    #define vdbg(...) 1
#endif

using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<string> vs;
typedef vector<pii> vpii;
typedef vector< vector<int> > vvi;

struct IoSetup {
  IoSetup() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(15);
    cerr << fixed << setprecision(15);
  }
} iosetup;

int gcd(int a, int b){if(a>b) swap(a,b); return a==0 ? b : gcd(b%a,a);} ll gcd(ll a, ll b){if(a>b) swap(a,b); return a==0 ? b : gcd(b%a,a);}
int lcm(int a, int b){return (a / gcd(a,b)) * b;} ll lcm(ll a, ll b){return (a / gcd(a,b)) * b;}
inline int pow(int a, int b){int ans = 1; rep(i,b) ans *= a; return ans;} inline ll pow(ll a, ll b){ll ans = 1; rep(i,b) ans*= a; return ans;}
inline ll pow(int a, ll b){ll ans = 1; rep(i,b) ans*= a; return ans;} inline ll pow(ll a, int b){ll ans = 1; rep(i,b) ans*= a; return ans;}
template<typename T, typename U> inline bool amin(T &x, U y) { return (y < x) ? (x = y, true) : false; }
template<typename T, typename U> inline bool amax(T &x, U y) { return (x < y) ? (x = y, true) : false; }
template<typename C> inline void _cin(C &c){cin >> c;}
template<typename T,typename U> inline void _cin(pair<T,U> &p){cin >> p.fi; cin >> p.se;}
template<typename C> inline void _cout(const C &c){cout << c;}
template<typename T,typename U> inline void _cout(const pair<T,U> &p){cout << p.fi << ' ' << p.se;}
void in(){} template <typename T,class... U> void in(T &t,U &...u){ _cin(t); in(u...);}
void out(){cout << endl;} template <typename T,class... U> void out(const T &t,U ...u){ _cout(t); if(sizeof...(u)) cout << ' '; out(u...);}
template<typename C> inline void in(vector<C> &v,int N=-1){if(sz(v) != 0){int M=(N == -1) ? sz(v) : N; rep(i,M) _cin(v[i]);}else{C c;rep(i,N) v.pb((_cin(c),c));}}
template<typename C> inline void in(C v[],int N){rep(i,N) _cin(v[i]);}
template<typename C> inline void out(const vector<C> &v,int N=-1){int M=(N == -1) ? sz(v) : N; rep(i,M) {cout<<( (i)?" ":"" ); _cout(v[i]);} cout<<endl; }
template<typename C> inline void out(C v[],int N){rep(i,N) {cout<<( (i)?" ":"" ); _cout(v[i]);} cout<<endl; }
template<typename C> inline void vector_debug(const vector<C> &v,int N=-1){cout << "{"; int M=(N == -1) ? sz(v) : N; rep(i,M) {cout<<( (i)?", ":"" ); _cout(v[i]);} cout<<"}"; }
template<typename C> inline void vector_debug(C v[], int N){cout << "{"; rep(i,N) {cout<<((i)?", ":""); _cout(*(v+i));} cout<<"}\n";}
void dbg_out(){cout << endl;} template <typename T,class... U> void dbg_out(const T &t,U ...u){ _cout(t); if(sizeof...(u)) cout << ", "; dbg_out(u...);}
template<typename C,class... U> void dbg_out(const vector<C> &v,U ...u){vector_debug(v); if(sizeof...(u)) cout << ", "; dbg_out(u...);}
template<typename C,class... U> void dbg_out(const vector<vector<C>> &v,U ...u){cout << "{ "; rep(i,sz(v)) {if(i)cout<<", "; vector_debug(v[i]);} cout << " }"; if(sizeof...(u)) cout << ", "; dbg_out(u...);}
template<typename C> inline C vmax(const vector<C> &v){C n=v[0]; rep(i,sz(v)) amax(n,v[i]); return n;} template<typename C> inline C vmax(C v[], int N){C n=v[0]; rep( i , N ) amax(n,v[i]); return n;}
template<typename C> inline C vmin(const vector<C> &v){C n=v[0]; rep(i,sz(v)) amin(n,v[i]); return n;} template<typename C> inline C vmin(C v[], int N){C n=v[0]; rep( i , N ) amin(n,v[i]); return n;}
template<typename C> inline C vsum(const vector<C> &v){C n=0; rep(i,sz(v)) n+=v[i]; return n;} template<typename C> inline C vsum(C v[], int N){C n=0; rep( i , N ) n+=v[i]; return n;}

////////////
/// main ///
////////////

// セグメント木
// 元の配列は0-indexedとする
// 元の配列のk番目の要素はノードk+size
// ノードkについて親ノードはk/2,子ノードは2k
template<typename T>
struct ST{
  int size;
  vector<T> seg;

  // ここから問題に応じて編集
  // func(a,INF)=aとなるようなINFを代入
  T INF = 0;
  // 結合則の成り立つ演算を書く
  T func(T a, T b){
    return a + b;
  }
  // ここまで
  
  ST(int N){
    size = 1;
    while(size < N) size <<= 1;
    seg.assign(2 * size, INF);
  }

  void set(int k,T& x){
    seg[k + size] = x;
  }

  void build(){
    for(int k=size-1; k>0; k--){
      seg[k] = func(seg[2 * k] , seg[2 * k + 1]);
    }
  }
  
  void update(int k){
    k += size; seg[k]++;
    while(k >>= 1){
      seg[k] = func(seg[2 * k] , seg[2 * k + 1]);
    }
  }
  
  T query(int a, int b){
    T L = INF, R = INF;
    for(a+=size,b+=size; a<b; a>>=1,b>>=1){
      if(a & 1) L = func(L,seg[a++]);
      if(b & 1) R = func(seg[--b],R);
      trc(L , R);
    }
    return func(L, R);
  }

  T operator[](const int &k) const{
    return seg[k + size];
  }

};

int main(){
  ini(N,Q);
  ST<ll> st(N);
  set<int> left,right;
  rep(i,N){
    inl(j);
    st.set(i, j);
  }
  st.build();
  rep(i,N){
    left.insert(i);
    right.insert(i);
  }
  rep(i,Q){
    ins(S); ini(x); x--;
    if(S == "1"){
      left.erase(x + 1);
      right.erase(x);
    }
    if(S == "2"){
      left.insert(x + 1);
      right.insert(x);
    }
    if(S == "3"){
      st.update(x);
    }
    if(S == "4"){
      auto itr = left.upper_bound(x);
      itr --;
      int l = *(itr);
      int r = *(right.lower_bound(x));
      trc(l,r);
      trc(st.seg[1] , st[0] , st[1]);
      out(st.query(l,r + 1));
    }
  }


}
0