結果

問題 No.868 ハイパー部分和問題
コンテスト
ユーザー tails
提出日時 2020-11-27 14:05:28
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 50 ms / 7,000 ms
コード長 1,160 bytes
コンパイル時間 1,007 ms
コンパイル使用メモリ 69,632 KB
最終ジャッジ日時 2025-01-16 06:04:21
ジャッジサーバーID
（参考情報） 		judge5 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 38
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:72:14: warning: ignoring return value of ‘ssize_t write(int, const void*, size_t)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   72 |         write(1,wbuf,q*2);
      |         ~~~~~^~~~~~~~~~~~

ソースコード

diff # 

#pragma GCC optimize("Ofast")
#pragma GCC target("avx2")

#include <sys/mman.h>
#include <unistd.h>
#include <bitset>

char*rp;

inline int rd_int(){
	int v=0;
	for(int c;c=*rp++-48,c>=0;)v=v*10+c;
	return v;
}

int n,k;

struct RangeVal {
	int st;
	int ed;
	int val;
};
RangeVal rv[30000],rvtmp[30000];

char wbuf[30000];

typedef std::bitset<15001> bst;

void f(int st,int ed,int l,int r,bst& bs){
	int tmpn=0,wn=l;
	for(int i=l;i<r;++i){
		if(rv[i].ed<=st||ed<=rv[i].st){
			rvtmp[tmpn++]=rv[i];
		}else if(rv[i].st<=st&&ed<=rv[i].ed){
			bs|=bs<<rv[i].val;
			rvtmp[tmpn++]=rv[i];
		}else{
			rv[wn++]=rv[i];
		}
	}
	for(int i=0;i<tmpn;++i){
		rv[wn+i]=rvtmp[i];
	}
	if(st==ed-1){
		wbuf[st*2+0]=bs[k]+48;
		wbuf[st*2+1]=10;
	}else{
		bst bs1=bs;
		f(st,st+ed>>1,l,wn,bs1);
		f(st+ed>>1,ed,l,wn,bs);
	}
}

int main(){
	rp=static_cast<char*>(mmap(0,1l<<28,1,2,0,0));
	n=rd_int();
	k=rd_int();
	for(int i=0;i<n;++i){
		rv[i]={0,15000,rd_int()};
	}
	int q=rd_int();
	for(int i=0;i<q;++i){
		int x=rd_int()-1;
		int v=rd_int();
		rv[n+i]={rv[x].st,i,rv[x].val};
		rv[x]={i,rv[x].ed,v};
	}

	bst bs;
	bs[0]=1;
	f(0,q,0,n+q,bs);
	write(1,wbuf,q*2);
	_exit(0);
}
0