結果

問題 No.1074 増殖
ユーザー SSRSSSRS
提出日時 2020-06-05 22:45:33
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
RE  
実行時間 -
コード長 6,597 bytes
コンパイル時間 2,689 ms
コンパイル使用メモリ 185,692 KB
実行使用メモリ 12,752 KB
最終ジャッジ日時 2024-05-09 22:26:04
合計ジャッジ時間 7,346 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 9 ms
11,728 KB
testcase_01 AC 9 ms
11,732 KB
testcase_02 AC 9 ms
11,728 KB
testcase_03 AC 9 ms
11,728 KB
testcase_04 AC 9 ms
11,728 KB
testcase_05 AC 9 ms
11,856 KB
testcase_06 AC 211 ms
12,372 KB
testcase_07 AC 388 ms
12,444 KB
testcase_08 RE -
testcase_09 AC 915 ms
12,368 KB
testcase_10 AC 150 ms
12,364 KB
testcase_11 RE -
testcase_12 AC 913 ms
12,368 KB
testcase_13 RE -
testcase_14 RE -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
long long INF = 1000000000;
template <typename T>
struct range_update_range_max{
	int N;
	vector<T> ST;
	vector<T> lazy;
	range_update_range_max(vector<T> A){
		int n = A.size();
		N = 1;
		while (N < n){
			N *= 2;
		}
		ST = vector<T>(N * 2 - 1, -INF);
		lazy = vector<T>(N * 2 - 1, -1);
		for (int i = 0; i < n; i++){
			ST[N - 1 + i] = A[i];
		}
		for (int i = N - 2; i >= 0; i--){
			ST[i] = max(ST[i * 2 + 1], ST[i * 2 + 2]);
		}
	}
	void eval(int i){
		if (lazy[i] != -1){
			if (i < N - 1){
				lazy[i * 2 + 1] = lazy[i];
				lazy[i * 2 + 2] = lazy[i];
			}
			ST[i] = lazy[i];
			lazy[i] = -1;
		}
	}
	void range_update(int L, int R, T x, int i, int l, int r){
		eval(i);
		if (R <= l || r <= L){
			return;
		} else if (L <= l && r <= R){
			lazy[i] = x;
			eval(i);
		} else {
			int m = (l + r) / 2;
			range_update(L, R, x, i * 2 + 1, l, m);
			range_update(L, R, x, i * 2 + 2, m, r);
			ST[i] = max(ST[i * 2 + 1], ST[i * 2 + 2]);
		}
	}
	void range_update(int L, int R, T x){
		return range_update(L, R, x, 0, 0, N);
	}
	T range_max(int L, int R, int i, int l, int r){
		eval(i);
		if (R <= l || r <= L){
			return -INF;
		} else if (L <= l && r <= R){
			return ST[i];
		} else {
			int m = (l + r) / 2;
			return max(range_max(L, R, i * 2 + 1, l, m), range_max(L, R, i * 2 + 2, m, r));
		}
	}
	T range_max(int L, int R){
		return range_max(L, R, 0, 0, N);
	}
};
template <typename T>
struct range_update_range_sum{
	int N;
	vector<T> ST;
	vector<T> lazy;
	range_update_range_sum(int n){
		N = 1;
		while (N < n){
			N *= 2;
		}
		ST = vector<T>(N * 2 - 1, 0);
		lazy = vector<T>(N * 2 - 1, -1);
	}
	void eval(int i, int l, int r){
		if (lazy[i] != -1){
			if (i < N - 1){
				lazy[i * 2 + 1] = lazy[i];
				lazy[i * 2 + 2] = lazy[i];
			}
			ST[i] = lazy[i] * (r - l);
			lazy[i] = -1;
		}
	}
	void range_update(int L, int R, T x, int i, int l, int r){
		eval(i, l, r);
		if (R <= l || r <= L){
			return;
		} else if (L <= l && r <= R){
			lazy[i] = x;
			eval(i, l, r);
		} else {
			int m = (l + r) / 2;
			range_update(L, R, x, i * 2 + 1, l, m);
			range_update(L, R, x, i * 2 + 2, m, r);
			ST[i] = ST[i * 2 + 1] + ST[i * 2 + 2];
		}
	}
	void range_update(int L, int R, T x){
		range_update(L, R, x, 0, 0, N);
	}
	T range_sum(int L, int R, int i, int l, int r){
		eval(i, l, r);
		if (R <= l || r <= L){
			return 0;
		} else if (L <= l && r <= R){
			return ST[i];
		} else {
			int m = (l + r) / 2;
			return range_sum(L, R, i * 2 + 1, l, m) + range_sum(L, R, i * 2 + 2, m, r);
		}
	}
	T range_sum(int L, int R){
		return range_sum(L, R, 0, 0, N);
	}
	T operator [](int k){
		return range_sum(k, k + 1);
	}
};
int main(){
  int N;
  cin >> N;
  vector<int> Xa(N), Ya(N), Xb(N), Yb(N);
  for (int i = 0; i < N; i++){
    cin >> Xa[i] >> Ya[i] >> Xb[i] >> Yb[i];
    Xa[i] = -Xa[i];
    Ya[i] += 20000;
    Yb[i] += 20000;
  }
  range_update_range_max<long long> left1(vector<long long>(40000, 0)), right1(vector<long long>(40000, 0));
  range_update_range_sum<long long> left2(40000), right2(40000);
  for (int i = 0; i < N; i++){
    long long ans = 0;
    if (left1.range_max(Ya[i], Yb[i]) <= Xa[i]){
      ans += (Yb[i] - Ya[i]) * Xa[i] - left2.range_sum(Ya[i], Yb[i]);
      left1.range_update(Ya[i], Yb[i], Xa[i]);
      left2.range_update(Ya[i], Yb[i], Xa[i]);
    } else {
      //find max-pos
      //ternary search
      int L = Ya[i] - 1;
      int R = Yb[i];
      while (R - L > 2){
        int mid1 = (L * 2 + R) / 3;
        int mid2 = (L + R * 2) / 3;
        if (left2[mid1] > left2[mid2]){
          R = mid2;
        } else {
          L = mid1;
        }
      }
      int pos = L;
      if (L + 1 < 40000){
        if (left2[L + 1] > left2[pos]){
          pos = L + 1;
        }
      }
      if (L + 2 < 40000){
        if (left2[L + 2] > left2[pos]){
          pos = L + 2;
        }
      }
      assert(left2[pos] > Xa[i]);
      if (left2[Ya[i]] <= Xa[i]){
        //binary search
        int tv = Ya[i];
        int fv = pos;
        while (fv - tv > 1){
          int mv = (tv + fv) / 2;
          if (left2[mv] <= Xa[i]){
            tv = mv;
          } else {
            fv = mv;
          }
        }
        ans += (fv - Ya[i]) * Xa[i] - left2.range_sum(Ya[i], fv);
        left1.range_update(Ya[i], fv, Xa[i]);
        left2.range_update(Ya[i], fv, Xa[i]);
      }
      if (left2[Yb[i] - 1] <= Xa[i]){
        //binary search
        int tv = Yb[i] - 1;
        int fv = pos;
        while (tv - fv > 1){
          int mv = (tv + fv) / 2;
          if (left2[mv] <= Xa[i]){
            tv = mv;
          } else {
            fv = mv;
          }
        }
        ans += (Yb[i] - tv) * Xa[i] - left2.range_sum(tv, Yb[i]);
        left1.range_update(tv, Yb[i], Xa[i]);
        left2.range_update(tv, Yb[i], Xa[i]);
      }
    }
    if (right1.range_max(Ya[i], Yb[i]) <= Xb[i]){
      ans += (Yb[i] - Ya[i]) * Xb[i] - right2.range_sum(Ya[i], Yb[i]);
      right1.range_update(Ya[i], Yb[i], Xb[i]);
      right2.range_update(Ya[i], Yb[i], Xb[i]);
    } else {
      //find max-pos
      //ternary search
      int L = Ya[i] - 1;
      int R = Yb[i];
      while (R - L > 2){
        int mid1 = (L * 2 + R) / 3;
        int mid2 = (L + R * 2) / 3;
        if (right2[mid1] > right2[mid2]){
          R = mid2;
        } else {
          L = mid1;
        }
      }
      int pos = L;
      if (L + 1 < 40000){
        if (right2[L + 1] > right2[pos]){
          pos = L + 1;
        }
      }
      if (L + 2 < 40000){
        if (right2[L + 2] > right2[pos]){
          pos = L + 2;
        }
      }
      //assert(right2[pos] > Xb[i]);
      if (right2[Ya[i]] <= Xb[i]){
        //binary search
        int tv = Ya[i];
        int fv = pos;
        while (fv - tv > 1){
          int mv = (tv + fv) / 2;
          if (right2[mv] <= Xb[i]){
            tv = mv;
          } else {
            fv = mv;
          }
        }
        ans += (fv - Ya[i]) * Xb[i] - right2.range_sum(Ya[i], fv);
        right1.range_update(Ya[i], fv, Xb[i]);
        right2.range_update(Ya[i], fv, Xb[i]);
      }
      if (right2[Yb[i] - 1] <= Xb[i]){
        //binary search
        int tv = Yb[i] - 1;
        int fv = pos;
        while (tv - fv > 1){
          int mv = (tv + fv) / 2;
          if (right2[mv] <= Xb[i]){
            tv = mv;
          } else {
            fv = mv;
          }
        }
        ans += (Yb[i] - tv) * Xb[i] - right2.range_sum(tv, Yb[i]);
        right1.range_update(tv, Yb[i], Xb[i]);
        right2.range_update(tv, Yb[i], Xb[i]);
      }
    }
    cout << ans << endl;
  }
}
0