結果
問題 | No.1074 増殖 |
ユーザー |
![]() |
提出日時 | 2020-06-05 22:34:21 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 519 ms / 2,000 ms |
コード長 | 7,144 bytes |
コンパイル時間 | 2,330 ms |
コンパイル使用メモリ | 137,968 KB |
最終ジャッジ日時 | 2025-01-10 22:45:07 |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 12 |
ソースコード
#line 1 "main.cpp"#include <algorithm>#include <array>#include <bitset>#include <cassert>#include <cctype>#include <cstdint>#include <cstdlib>#include <cmath>#include <complex>#include <chrono>#include <deque>#include <functional>#include <iomanip>#include <iostream>#include <map>#include <memory>#include <numeric>#include <queue>#include <set>#include <stack>#include <string>#include <unordered_map>#include <vector>#include <random>#include <utility>#include <limits>#include <list>#include <type_traits>/* template start */#define rep(i, a, b) for (long long i = (a); (i) < (b); (i)++)#define all(i) i.begin(), i.end()#ifdef LOCAL#define debug(...) std::cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)#else#define debug(...)#endifvoid debug_out(){std::cerr<<std::endl;}template<typename Head,typename... Tail>void debug_out(Head h,Tail... t){std::cerr<<" "<<h;if(sizeof...(t)>0)std::cout<<" :";debug_out(t...);}template <typename T1, typename T2>std::ostream& operator<<(std::ostream& os, std::pair<T1, T2> pa) {return os << pa.first << " " << pa.second;}template <typename T>std::ostream& operator<<(std::ostream& os, std::vector<T> vec) {for (std::size_t i = 0; i < vec.size(); i++)os << vec[i] << (i + 1 == vec.size() ? "" : " ");return os;}template<typename T1,typename T2>inline bool chmax(T1& a,T2 b){return a<b && (a=b,true);}template<typename T1,typename T2>inline bool chmin(T1& a,T2 b){return a>b && (a=b,true);}template<typename Num>constexpr Num mypow(Num a, long long b) {if(b==0)return 1;if (a==0)return 0;Num x = 1;while (b > 0) {if(b & 1)x*=a;a*=a;b >>= 1;}return x;}template <std::uint_fast64_t Modulus> class modint {using u64 = std::uint_fast64_t;public:u64 a;constexpr modint(const u64 x = 0) noexcept : a(x % Modulus) {}constexpr u64 &value() noexcept { return a; }constexpr const u64 &value() const noexcept { return a; }constexpr bool operator==(const modint rhs) const noexcept {return a==rhs.a;}constexpr bool operator!=(const modint rhs) const noexcept {return !(*this==rhs);}constexpr modint operator+(const modint rhs) const noexcept {return modint(*this) += rhs;}constexpr modint operator-(const modint rhs) const noexcept {return modint(*this) -= rhs;}constexpr modint operator*(const modint rhs) const noexcept {return modint(*this) *= rhs;}constexpr modint operator/(const modint rhs) const noexcept {return modint(*this) /= rhs;}constexpr modint &operator+=(const modint rhs) noexcept {a += rhs.a;if (a >= Modulus) {a -= Modulus;}return *this;}constexpr modint &operator-=(const modint rhs) noexcept {if (a < rhs.a) {a += Modulus;}a -= rhs.a;return *this;}constexpr modint &operator*=(const modint rhs) noexcept {a = a * rhs.a % Modulus;return *this;}constexpr modint &operator/=(modint rhs) noexcept {u64 exp = Modulus - 2;while (exp) {if (exp % 2) {*this *= rhs;}rhs *= rhs;exp /= 2;}return *this;}};/* template end */using ll = long long;#line 2 "/mnt/c/Users/Imperi/Documents/cp-library/lib/SegmentTree/LazySegmentTree.cpp"#line 5 "/mnt/c/Users/Imperi/Documents/cp-library/lib/SegmentTree/LazySegmentTree.cpp"//Lazy// type value_t// type lazy_t// static value_t id_val// static value_t id_lazy// static (value_t,value_t) -> value_t f// static (value_t,lazy_t) -> value_t g// static (lazy_t,lazy_t) -> lazy_t h// static (lazy_t,size_t) -> lazy_t p/* Lazy templatestruct Lazy{using value_t= ~~ ;using lazy_t= ~~ ;static constexpr value_t id_val= ~~ ;static constexpr lazy_t id_lazy= ~~ ;static value_t f(value_t a,value_t b){return ~~ ;}static value_t g(value_t a,lazy_t b){return ~~ ;}static lazy_t h(lazy_t a,lazy_t b){return ~~ ;}static lazy_t p(lazy_t a,std::size_t n){return ~~ ;}};*/template<typename Lazy>class LazySegmentTree{public:using value_t=typename Lazy::value_t;using lazy_t=typename Lazy::lazy_t;using size_t=std::size_t;private:size_t n,n0;std::vector<value_t> val;std::vector<lazy_t> lazy;value_t update(size_t a,size_t b,lazy_t laz,size_t l,size_t r,size_t k){if(lazy[k]!=Lazy::id_lazy){if(k<n0-1){lazy[2*k+1]=Lazy::h(lazy[2*k+1],lazy[k]);lazy[2*k+2]=Lazy::h(lazy[2*k+2],lazy[k]);}val[k]=Lazy::g(val[k],Lazy::p(lazy[k],r-l));lazy[k]=Lazy::id_lazy;}if(r<=a||b<=l)return val[k];if(a<=l&&r<=b){lazy[k]=Lazy::h(lazy[k],laz);return Lazy::g(val[k],Lazy::p(lazy[k],r-l));}return val[k]=Lazy::f(update(a,b,laz,l,l+(r-l)/2,2*k+1),update(a,b,laz,l+(r-l)/2,r,2*k+2));}value_t fold(size_t a,size_t b,size_t l,size_t r,size_t k){if(lazy[k]!=Lazy::id_lazy){if(k<n0-1){lazy[2*k+1]=Lazy::h(lazy[2*k+1],lazy[k]);lazy[2*k+2]=Lazy::h(lazy[2*k+2],lazy[k]);}val[k]=Lazy::g(val[k],Lazy::p(lazy[k],r-l));lazy[k]=Lazy::id_lazy;}if(r<=a||b<=l)return Lazy::id_val;if(a<=l&&r<=b)return val[k];return Lazy::f(fold(a,b,l,l+(r-l)/2,2*k+1),fold(a,b,l+(r-l)/2,r,2*k+2));}inline size_t beki(size_t n_){size_t ret=1;while(ret<n_)ret<<=1;return ret;}public:LazySegmentTree(size_t n_):n(n_),n0(beki(n)),val(2*n0-1,Lazy::id_val),lazy(2*n0-1,Lazy::id_lazy){}LazySegmentTree(std::vector<value_t> val_):n(val_.size()),n0(beki(n)),val(2*n0-1,Lazy::id_val),lazy(2*n0-1,Lazy::id_lazy){for(size_t i=0;i<n;i++)val[i+n0-1]=val_[i];for(long long i=n0-2;i>=0;i--)val[i]=Lazy::f(val[2*i+1],val[2*i+2]);}void update(size_t a,size_t b,lazy_t laz){update(a,b,laz,0,n0,0);}value_t fold(size_t a,size_t b){return fold(a,b,0,n0,0);}};#line 139 "main.cpp"constexpr ll INF=1e9+7;struct Lazy{using value_t=ll;using lazy_t=ll;static constexpr value_t id_val=0;static constexpr lazy_t id_lazy=INF;static value_t f(value_t a,value_t b){return a+b ;}static value_t g(value_t a,lazy_t b){if(b!=id_lazy)return b;return a;}static lazy_t h(lazy_t a,lazy_t b){if(b!=id_lazy)return b;return a;}static lazy_t p(lazy_t a,std::size_t n){return a*n; ;}};int main() {std::cin.tie(nullptr);std::ios::sync_with_stdio(false);ll n;std::cin>>n;std::vector<LazySegmentTree<Lazy>> seg(4,LazySegmentTree<Lazy>(20100));while(n--){ll po[4];rep(i,0,4)std::cin>>po[i];rep(i,0,2)po[i]*=-1;ll ans=0;rep(i,0,4){ll x=po[i],y=po[(i+1)%4];ans+=x*y;ll l=-1,r=20100;while(r-l>1){ll mid=l+(r-l)/2;if(seg[i].fold(mid,mid+1)>y)l=mid;else r=mid;}ans-=y*std::min(x,l+1);if(r<x){ans-=seg[i].fold(r,x);seg[i].update(r,x,y);}}std::cout<<ans<<"\n";}return 0;}