제출 #1335163

#제출 시각아이디문제언어결과실행 시간메모리
1335163developinpopFancy Fence (CEOI20_fancyfence)C++20
0 / 100
4 ms3348 KiB
/*
_____________________.
|____________________|   $$\                                                            $$\           $$\        $$\               
|____________________|   $$ |                                                           \__|          $$ |       $$ |              
|____________________| $$$$$$\    $$$$$$\  $$$$$$\  $$$$$$$\   $$$$$$$\        $$$$$$\  $$\  $$$$$$\  $$$$$$$\ $$$$$$\    $$$$$$$\ 
|____________________| \_$$  _|  $$  __$$\ \____$$\ $$  __$$\ $$  _____|      $$  __$$\ $$ |$$  __$$\ $$  __$$\\_$$  _|  $$  _____|
|____________________|   $$ |    $$ |  \__|$$$$$$$ |$$ |  $$ |\$$$$$$\        $$ |  \__|$$ |$$ /  $$ |$$ |  $$ | $$ |    \$$$$$$\  
                         $$ |$$\ $$ |     $$  __$$ |$$ |  $$ | \____$$\       $$ |      $$ |$$ |  $$ |$$ |  $$ | $$ |$$\  \____$$\ 
                         \$$$$  |$$ |     \$$$$$$$ |$$ |  $$ |$$$$$$$  |      $$ |      $$ |\$$$$$$$ |$$ |  $$ | \$$$$  |$$$$$$$  |
            へ   ♡        \____/ \__|      \_______|\__|  \__|\_______/       \__|      \__| \____$$ |\__|  \__|  \____/ \_______/ 
         ૮ - ՛)                                                                             $$\   $$ |    
         / ⁻ ៸|                                                                              \$$$$$$  |   are human rights :3
     乀 (ˍ,ل ل                                                                               \______/ 
 
*/
 
#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;

template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, 
                         tree_order_statistics_node_update>;
template <typename T>
using ordered_multiset = tree<pair<T, long long>, null_type, 
                      less<pair<T, long long>>, rb_tree_tag, 
                         tree_order_statistics_node_update>;
 
using namespace std;
using namespace __gnu_pbds;
 
#define ll long long
#define ull unsigned long long
#define ld long double
#define inf (ll)2e18+4
#define pb push_back
#define se second
#define fi first
#define endl '\n'
#define mp make_pair
#define pll pair<ll,ll>
#define kth_smallest find_by_order
#define num_of_smaller order_of_key
#define fori(x) for(ll i=0;i<x;i++)
#define forj(y) for(ll j=0;j<y;j++)
#define fork(z) for(ll k=0;k<z;k++)
#define forl(a) for(ll l=0;l<a;l++)
 
#define DEBUG
 
#ifdef DEBUG
#define show(x) cerr<<#x<<" is "<<x<<endl;
#define show2(x,y) cerr<<#x<<" is "<<x<<" "<<#y<<" is "<<y<<endl;
#define show3(x,y,z) cerr<<#x<<" is "<<x<<" "<<#y<<" is "<<y<<" "<<#z<<" is "<<z<<endl;
#define show4(x,y,z,a) cerr<<#x<<" is "<<x<<" "<<#y<<" is "<<y<<" "<<#z<<" is "<<z<<" "<<#a<<" is "<<a<<endl;
#define show_vec(a) for(auto &i:a)cerr<<i<<" ";cerr<<endl;
#define skillissue cerr<<"your code is running\n";
#define getchar_unlocked _getchar_nolock // comment before submission
#else
#define show(x)
#define show2(x,y)
#define show3(x,y,z)
#define show4(x,y,z,a)
#define show_vec(a)
#define skillissue
#endif
 
/*
 
inline int readint() {
    int x=0; char ch=getchar_unlocked(); bool s=1;
    while(ch<'0'||ch>'9'){if(ch=='-')s=0;ch=getchar_unlocked();}
    while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar_unlocked();}
    return s?x:-x;
}
 
*/


const ll mod=1e9+7;


ll summ(ll x,ll y){
	return ((x+y)*(y-x+1)/2) % mod;
}


struct node{
	ll S,E,val,lazyset,lazyadd,M;
	node *l,*r;
	node(ll s,ll e){
		S=s;E=e;val=0,lazyset=-1,lazyadd=0;
		M=(S+E)/2;
		if(S==E)return;
		l=nullptr;
		r=nullptr;
	}
	void prop(){
		if(S==E)return;
		if(l==nullptr){
			l=new node(S,M);
			r=new node(M+1,E);
		}
		if(lazyset!=-1){
			l->lazyset=lazyset;
			l->val=(summ(l->S,l->E)*lazyset)%mod;
			r->lazyset=lazyset;
			r->val=(summ(r->S,r->E)*lazyset)%mod;
			lazyset=-1;
			lazyadd=0;
		}else{
			l->lazyadd=lazyadd;
			l->val=(l->val+(summ(l->S,l->E)*lazyadd)%mod)%mod;
			r->lazyadd=lazyadd;
			r->val=(r->val+(summ(r->S,r->E)*lazyadd)%mod)%mod;
			lazyadd=0;
		}
	}
	ll qry(){
		return val;
	}
	void set(ll x,ll y,ll v){
		//show4(x,y,E,S)
		if(x>E or y<S)return;
		prop();
		if(x<=S and E<=y){
			val=summ(S,E)*v;
			lazyset=v;
			if(lazyadd!=0)lazyadd=0;
			return;
		}
		prop();
		l->set(x,y,v);
		r->set(x,y,v);
		val=(l->val+r->val)%mod;
	}
	void add(ll x,ll y,ll v){
		//show4(x,y,E,S)
		if(x>E or y<S)return;
		prop();
		if(x<=S and E<=y){
			val=(val+summ(S,E)*v)%mod;
			lazyadd+=v;
			return;
		}
		prop();
		l->add(x,y,v);
		r->add(x,y,v);
		val=(l->val+r->val)%mod;
	}
};


int32_t main(){
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	ll n;cin>>n;
	ll h[n],b[n];
	fori(n)cin>>h[i]>>b[i];
	node *root=new node(0,1e9+4);
	ll ans=0;
	fori(n){
		root->set(h[i]+1,1e9+4,0);
		root->add(0,h[i],b[i]);
		ans = ((ans + root->qry())%mod + ((b[i]%mod * (h[i]*(h[i]+1)/2)%mod)%mod))%mod;
		
	}
	cout<<ans%mod;
	
	
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...