結果

問題 No.1074 増殖
ユーザー minatominato
提出日時 2020-06-05 23:58:55
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 187 ms / 2,000 ms
コード長 4,879 bytes
コンパイル時間 5,494 ms
コンパイル使用メモリ 252,680 KB
実行使用メモリ 11,648 KB
最終ジャッジ日時 2024-05-10 00:28:04
合計ジャッジ時間 7,013 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 10 ms
11,520 KB
testcase_01 AC 9 ms
11,520 KB
testcase_02 AC 9 ms
11,520 KB
testcase_03 AC 10 ms
11,520 KB
testcase_04 AC 10 ms
11,520 KB
testcase_05 AC 9 ms
11,520 KB
testcase_06 AC 60 ms
11,520 KB
testcase_07 AC 78 ms
11,648 KB
testcase_08 AC 93 ms
11,520 KB
testcase_09 AC 187 ms
11,520 KB
testcase_10 AC 59 ms
11,648 KB
testcase_11 AC 48 ms
11,520 KB
testcase_12 AC 48 ms
11,520 KB
testcase_13 AC 122 ms
11,520 KB
testcase_14 AC 122 ms
11,520 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
using ll = long long;
using u64 = uint_fast64_t;
using pii =  pair<int, int>;
using pll =  pair<long long, long long>;
#define rep(i, n) for(int i = 0; i < (n); ++i)
#define all(x) (x).begin(),(x).end()
constexpr char ln =  '\n';
constexpr long long MOD = 1000000007;
//constexpr long long MOD = 998244353;
template<class T1, class T2> inline bool chmax(T1 &a, T2 b) { if (a < b) { a = b; return true;} return false; }
template<class T1, class T2> inline bool chmin(T1 &a, T2 b) { if (a > b) { a = b; return true;} return false; }
inline int popcount(int x) {return __builtin_popcount(x);}
inline int popcount(long long x) {return __builtin_popcountll(x);}
void print() { cout << "\n"; }
template<class T, class... Args>
void print(const T &x, const Args &... args) {
    cout << x << " ";
    print(args...);
}
///////////////////////////////////////////////////////////////////////////////////////////////////////////////

constexpr int inf = 2e9;
struct SegtreeBeats{
	vector<int>mx,smx,mxc;
	vector<int>mn,smn,mnc;
	vector<int>sum,lazy;
	int size=1;
	void update_node_max(int k,int x){
		sum[k]+=(x-mx[k])*mxc[k];
		if(mx[k]==mn[k]){
			mx[k]=mn[k]=x;
		}else if(mx[k]==smn[k]){
			mx[k]=smn[k]=x;
		}else {
			mx[k]=x;
		}
	}
	void update_node_min(int k,int x){
		sum[k]+=(x-mn[k])*mnc[k];
		if(mx[k]==mn[k]){
			mx[k]=mn[k]=x;
		}else if(smx[k]==mn[k]){
			smx[k]=mn[k]=x;
		}else {
			mn[k]=x;
		}
	}
	void update_node_add(int k,int len,int x){
		mx[k]+=x;
		if(smx[k]!=-inf)smx[k]+=x;
		mn[k]+=x;
		if(smn[k]!=inf)smn[k]+=x;
		sum[k]+=x*len;
		lazy[k]+=x;
	}
	void push(int k,int len){
		if(k>=size-1)return;
		if(lazy[k]!=0){
			update_node_add(k*2+1,len/2,lazy[k]);
			update_node_add(k*2+2,len/2,lazy[k]);
			lazy[k]=0;
		}
		if(mx[k*2+1]>mx[k])update_node_max(k*2+1,mx[k]);
		if(mx[k*2+2]>mx[k])update_node_max(k*2+2,mx[k]);
		if(mn[k*2+1]<mn[k])update_node_min(k*2+1,mn[k]);
		if(mn[k*2+2]<mn[k])update_node_min(k*2+2,mn[k]);
	}
	void update(int k){
		sum[k]=sum[k*2+1]+sum[k*2+2];
		if(mx[2*k+1]<mx[2*k+2]){
			mx[k]=mx[2*k+2];
			mxc[k]=mxc[2*k+2];
			smx[k]=max(mx[2*k+1],smx[2*k+2]);
		}else if(mx[2*k+1]>mx[2*k+2]){
			mx[k]=mx[2*k+1];
			mxc[k]=mxc[2*k+1];
			smx[k]=max(smx[2*k+1],mx[2*k+2]);
		}else {
			mx[k]=mx[2*k+1];
			mxc[k]=mxc[2*k+1]+mxc[2*k+2];
			smx[k]=max(smx[2*k+1],smx[2*k+2]);
		}
		if(mn[2*k+1]<mn[2*k+2]){
			mn[k]=mn[2*k+1];
			mnc[k]=mnc[2*k+1];
			smn[k]=min(smn[2*k+1],mn[2*k+2]);
		}else if(mn[2*k+1]>mn[2*k+2]){
			mn[k]=mn[2*k+2];
			mnc[k]=mnc[2*k+2];
			smn[k]=min(mn[2*k+1],smn[2*k+2]);
		}else {
			mn[k]=mn[2*k+1];
			mnc[k]=mnc[2*k+1]+mnc[2*k+2];
			smn[k]=min(smn[2*k+1],smn[2*k+2]);
		}
	}
	void update_min(int a,int b,int x,int k=0,int l=0,int r=-1){
		if(r==-1)r=size;
		if(r<=a||b<=l||mx[k]<=x)return;
		if(a<=l&&r<=b&&smx[k]<x){
			update_node_max(k,x);
			return;
		}
		push(k,r-l);
		update_min(a,b,x,k*2+1,l,(l+r)/2);
		update_min(a,b,x,k*2+2,(l+r)/2,r);
		update(k);
	}
	void update_max(int a,int b,int x,int k=0,int l=0,int r=-1){
		if(r==-1)r=size;
		if(r<=a||b<=l||mn[k]>=x)return;
		if(a<=l&&r<=b&&smn[k]>x){
			update_node_min(k,x);
			return;
		}
		push(k,r-l);
		update_max(a,b,x,k*2+1,l,(l+r)/2);
		update_max(a,b,x,k*2+2,(l+r)/2,r);
		update(k);
	}
	void update_add(int a,int b,int x,int k=0,int l=0,int r=-1){
		if(r==-1)r=size;
		if(r<=a||b<=l)return;
		if(a<=l&&r<=b){
			update_node_add(k,r-l,x);
			return;
		}
		push(k,r-l);
		update_add(a,b,x,k*2+1,l,(l+r)/2);
		update_add(a,b,x,k*2+2,(l+r)/2,r);
		update(k);
	}
	void set(int k,int x){
		k+=size-1;
		mx[k]=x;mn[k]=x;sum[k]=x;
	}
	void init(){
		for(int i=size-2;i>=0;i--)update(i);
	}
	int query_sum(int a,int b,int k=0,int l=0,int r=-1){
		if(r==-1)r=size;
		if(r<=a||b<=l)return 0;
		if(a<=l&&r<=b)return sum[k];
		push(k,r-l);
		int lv=query_sum(a,b,k*2+1,l,(l+r)/2);
		int rv=query_sum(a,b,k*2+2,(l+r)/2,r);
		return lv+rv;
	}
	SegtreeBeats(int x){
		while(size<x)size*=2;
		mx.resize(size*2-1);smx.resize(size*2-1,-inf);mxc.resize(size*2-1,1);
		mn.resize(size*2-1);smn.resize(size*2-1,inf);mnc.resize(size*2-1,1);
		sum.resize(size*2-1);lazy.resize(size*2-1);
	}
};
const int MAX = 40010;
int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int N; cin >> N;

    SegtreeBeats seg1(MAX),seg2(MAX);
    //cout << "!!!"  << endl;
    rep(i,MAX) {
        seg1.set(i,0);
        seg2.set(i,0);
    }

    seg1.init(); seg2.init();
    ll val = 0;
    rep(_,N) {
        int x1,y1,x2,y2; cin >> x1 >> y1 >> x2 >> y2;
        x1 += 20000; x2 += 20000;
        seg1.update_max(x1,x2,-y1);
        seg2.update_max(x1,x2,y2);
        ll cur = seg1.query_sum(0,40000) + seg2.query_sum(0,40000);
        cout << cur - val << ln;
        val = cur;
    }
}
0