結果

問題 No.1786 Maximum Suffix Median (Online)
ユーザー 沙耶花沙耶花
提出日時 2021-12-15 01:17:35
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
MLE  
実行時間 -
コード長 4,091 bytes
コンパイル時間 2,514 ms
コンパイル使用メモリ 206,428 KB
実行使用メモリ 825,840 KB
最終ジャッジ日時 2023-10-01 02:17:07
合計ジャッジ時間 7,595 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge15
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 MLE -
testcase_01 AC 2 ms
4,376 KB
testcase_02 AC 2 ms
4,376 KB
testcase_03 AC 4 ms
4,376 KB
testcase_04 AC 4 ms
4,376 KB
testcase_05 AC 5 ms
5,288 KB
testcase_06 AC 3 ms
4,376 KB
testcase_07 AC 3 ms
4,380 KB
testcase_08 TLE -
testcase_09 -- -
testcase_10 -- -
testcase_11 -- -
testcase_12 -- -
testcase_13 -- -
testcase_14 -- -
testcase_15 -- -
testcase_16 -- -
testcase_17 -- -
testcase_18 -- -
testcase_19 -- -
testcase_20 -- -
testcase_21 -- -
testcase_22 -- -
testcase_23 -- -
testcase_24 -- -
testcase_25 -- -
testcase_26 -- -
testcase_27 -- -
testcase_28 -- -
testcase_29 -- -
testcase_30 -- -
testcase_31 -- -
testcase_32 -- -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <stdio.h>
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<(n);i++)
#define Inf 1000000001

template <class S,
          S (*op)(S, S),
          S (*e)(),
          class F,
          S (*mapping)(F, S),
          F (*composition)(F, F),
          F (*id)()>
struct dynamic_lazy_segtree {
	struct node{
		int nxt[2];
		S v;
		F lz;
		node(){
			nxt[0] = -1;
			nxt[1] = -1;
			v = e();
			lz = id();
		}
	};
	
	vector<node> nodes;
	
	dynamic_lazy_segtree() : dynamic_lazy_segtree(0) {}
	dynamic_lazy_segtree(long long n){
		log = 0;
		while((1LL<<log) < n){
			log++;
		}
		_n = n;
		nodes.resize(1,node());
	}
	
	int get(int cur,int ind){
		if(nodes[cur].nxt[ind]==-1){
			nodes[cur].nxt[ind] = nodes.size();
			nodes.push_back(node());
		}
		
		return nodes[cur].nxt[ind];
	}
	
	void set(long long p, S x) {
        assert(0 <= p && p < _n);
		vector<int> t(1,0);
        for(int i=log-1;i>=0;i--){
			t.push_back(get(t.back(),(p>>i)&1));
		}
		
		rep(i,t.size()-1){
			push(t[i]);
		}
		reverse(t.begin(),t.end());
		rep(i,t.size()){
			if(i==0)nodes[t[i]].v = x;
			else{
				update(t[i]);
			}
		}
    }
	
	S get(long long p) {
        assert(0 <= p && p < _n);
		int cur = 0;
        for(int i=log-1;i>=0;i--){
			push(cur);
			cur = get(cur,(p>>i)&1);
		}
		return nodes[cur].v;
    }
	
	S prod(long long l,long long r,int cur,int depth){
		if(cur==-1||r-l==0)return e();
		if(r-l==(1LL<<depth))return nodes[cur].v;
		push(cur);
		r--;
		if((l>>(depth-1))&1){
			l ^= 1LL<<(depth-1);
			r ^= 1LL<<(depth-1);
			return prod(l,r+1,nodes[cur].nxt[1],depth-1);
		}
		if(((r>>(depth-1))&1)==0){
			return prod(l,r+1,nodes[cur].nxt[0],depth-1);
		}

		r ^= 1LL<<(depth-1);
		return op(prod(l,1LL<<(depth-1),nodes[cur].nxt[0],depth-1),prod(0,r+1,nodes[cur].nxt[1],depth-1));
	}
	
	S prod(long long l, long long r) {
        assert(0 <= l && l <= r && r <= _n);
        return prod(l,r,0,log);
    }

	S all_prod() { return nodes[0].v; }
	
	void apply(long long p,F f){
		assert(0 <= p && p < _n);
		vector<int> t(1,0);
        for(int i=log-1;i>=0;i--){
			t.push_back(get(t.back(),(p>>i)&1));
		}
		
		rep(i,t.size()-1){
			push(t[i]);
		}
		reverse(t.begin(),t.end());
		rep(i,t.size()){
			if(i==0)nodes[t[i]].v = mapping(f,nodes[t[i]].v);
			else{
				update(t[i]);
			}
		}		
	}
	
	void apply(long long l,long long r,int cur,int depth,F f){
		if(r-l==0)return;
		if(r-l==(1LL<<depth)){
			all_apply(cur,f);
			return;
		}
		push(cur);
		r--;
		if((l>>(depth-1))&1){
			l ^= 1LL<<(depth-1);
			r ^= 1LL<<(depth-1);
			apply(l,r+1,get(cur,1),depth-1,f);
		}
		else if(((r>>(depth-1))&1)==0){
			apply(l,r+1,get(cur,0),depth-1,f);
		}
		else{
			r ^= 1LL<<(depth-1);
			apply(l,1LL<<(depth-1),get(cur,0),depth-1,f);
			apply(0,r+1,get(cur,1),depth-1,f);
		}
		
		update(cur);
		return;
	}
	
	void apply(long long l,long long r,F f){
		assert(0 <= l && l <= r && r <= _n);
        apply(l,r,0,log,f);
	}
	

	void update(int k){
		nodes[k].v = e();
		rep(i,2){
			if(nodes[k].nxt[i]==-1)continue;
			nodes[k].v = op(nodes[k].v,nodes[nodes[k].nxt[i]].v);
		}
	}
	
	void all_apply(int k, F f) {
        nodes[k].v = mapping(f, nodes[k].v);
        nodes[k].lz = composition(f, nodes[k].lz);
    }
    void push(int k) {
		rep(i,2){
			int t = get(k,i);
			all_apply(t,nodes[k].lz);
		}
		nodes[k].lz = id();
    }
	
	long long _n,log;
	
};

int op(int a,int b){
	return max(a,b);
}

int e(){
	return 0;
}

int mapping(int a,int b){
	return a+b;
}

int composition(int a,int b){
	return a+b;
}

int id(){
	return 0;
}

int main(){
	
	int last = 0;
	
	dynamic_lazy_segtree<int,op,e,int,mapping,composition,id> seg((1<<30)+5);
	
	
	int N;
	scanf("%d",&N);
	
	rep(i,N){
		int A;
		scanf("%d",&A);
		A ^= last;
		seg.apply(0,A+1,1);
		int ok = A+1,ng = (1<<30)+1;
		while(ng-ok>1){
			int mid = (ok+ng)/2;
			if(seg.get(mid-1)==0)ng = mid;
			else ok = mid;
		}
		seg.apply(A+1,ok,-1);
		ok = 0,ng = (1<<30)+1;
		while(ng-ok>1){
			int mid = (ok+ng)/2;
			if(seg.get(mid)==0)ng = mid;
			else ok = mid;
		}
		printf("%d\n",ok);
		last = ok;
	}
	
	
	return 0;
}
0