QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#547849#8536. Lazy Cow-Ofast#Compile Error//C++176.4kb2024-09-05 11:23:102024-09-05 11:23:10

Judging History

你现在查看的是最新测评结果

  • [2024-09-05 11:23:10]
  • 评测
查看
  • [2024-09-05 11:23:10]
  • 提交

answer

#include <bits/stdc++.h>
#define mp make_pair
#define fir first
#define sec second
#define int long long
using namespace std;
const int N=2e5+10,mod=1e9+7;#include <bits/stdc++.h>
#define mp make_pair
#define fir first
#define sec second
#define int long long
using namespace std;
const int N=2e5+10,mod=1e9+7,maxv=1e6;
int D;
int qpow(int a,int b){
	b--;if(b==-1)return 0;
	int res=1;a%=mod;
	while(b){
		if(b&1)res=res*a%mod;
		a=a*a%mod;b>>=1;
	}return res;
}
pair <int,int> q[N];
namespace seg{
	int tree[(maxv+10)<<4],tag[(maxv+10)<<4];
	void pushdown(int rt,int left,int right){
		int mid=(left+right)>>1;
		if(tag[rt]){
			tag[rt<<1]+=tag[rt];
			tag[rt<<1|1]+=tag[rt];
			tree[rt<<1]+=(tag[rt]*(mid-left+1));
			tree[rt<<1|1]+=(tag[rt]*(right-mid));
			tag[rt]=0;
		}
	}
	void pushup(int rt){tree[rt]=tree[rt<<1]+tree[rt<<1|1];}
	void update(int rt,int left,int right,int L,int R,int x){
		if(left<right)pushdown(rt,left,right);
		if(left>=L&&right<=R){
			tag[rt]+=x;
			tree[rt]+=x*(right-left+1);
			return;
		}int mid=(left+right)>>1;
		if(L<=mid)update(rt<<1,left,mid,L,R,x);
		if(mid<R)update(rt<<1|1,mid+1,right,L,R,x);
		pushup(rt);
	}
	int query(int rt,int left,int right,int L,int R){
		if(left<right)pushdown(rt,left,right);
		if(left>=L&&right<=R)return tree[rt];
		int mid=(left+right)>>1,res=0;
		if(L<=mid)res+=query(rt<<1,left,mid,L,R);
		if(mid<R)res+=query(rt<<1|1,mid+1,right,L,R);
		return res;
	}
}
struct node{
	int l,r,s;
	bool operator <(const node b)const{
		if(r!=b.r)return r<b.r;
		return l<b.l;
	}
};
int ans=0;
set <node> S;
void modify(int x,int w){
	w=w-seg::query(1,1,maxv,1,x);
	//cout<<w<<endl;
	if(w<=0)return;
	//cout<<"YES!"<<endl;
	auto it=S.lower_bound((node){0,x,0});auto tmp=it;
	if(x!=tmp->r){
		S.insert((node){tmp->l,x,tmp->s});
		S.insert((node){x+1,tmp->r,tmp->s});
		S.erase(tmp);
	}
	it=S.lower_bound((node){0,x,0});
	auto pre=it;pre--;
	//cout<<"FUCK!"<<endl;
	//for(auto it:S){
	//	cout<<it.l<<" "<<it.r<<" "<<it.s<<endl;
	//}
	int Tmp=w;
	while(w){
		int Top=pre->s,sz=(it->r)-(it->l)+1,p=it->s;
		if(w>=(Top-p)*sz){
			w-=(Top-p)*sz;
			ans-=qpow(3,p)*sz%mod;
			ans+=qpow(3,Top)*sz%mod;
			seg::update(1,1,maxv,it->l,it->r,Top-p);
			ans%=mod;ans+=mod;ans%=mod;
			int L=pre->l,R=it->r;
			S.erase(pre);
			it=S.lower_bound((node){0,x,0});
			S.erase(it);
			it=S.insert((node){L,R,Top}).fir;
			pre=it;pre--;
		}else{
			int to=w/sz,m=w%sz;w=0;
			seg::update(1,1,maxv,it->l,it->r,to);
			if(m){
				ans-=qpow(3,p)*sz%mod;
				p+=to;sz-=m;
				ans+=qpow(3,p)*sz%mod;
				ans+=qpow(3,p+1)*m%mod;
				ans%=mod;ans+=mod;ans%=mod;
				int L=it->l,R=it->r;
				S.erase(it);
				seg::update(1,1,maxv,L,L+m-1,1);
				S.insert((node){L+m,R,p});
				it=(S.insert((node){L,L+m-1,p+1})).fir;
			}else{
				ans-=qpow(3,p)*sz%mod;
				p+=to;
				int L=it->l,R=it->r;
				S.erase(it);
				it=(S.insert((node){L,R,p})).fir;
				ans+=qpow(3,p)*sz%mod;
				ans%=mod;ans+=mod;ans%=mod;
			}
		}
	}
	//cout<<"S: "<<endl;
	//for(auto it:S){
	//	cout<<it.l<<" "<<it.r<<" "<<it.s<<endl;
	//}
	if(x==1e6)return;
	x++;w=min(Tmp,seg::query(1,1,maxv,x,maxv));
	it=S.lower_bound((node){0,x,0});
	pre=it;pre++;
	while(w){
		int Top=pre->s,sz=(it->r)-(it->l)+1,p=it->s;
		//cout<<"lr: "<<(it->l)<<" "<<(it->r)<<" "<<w<<" "<<p<<" "<<Top<<endl;
		if(w>=(p-Top)*sz){
			w-=(p-Top)*sz;
			ans-=qpow(3,p)*sz%mod;
			ans+=qpow(3,Top)*sz%mod;
			seg::update(1,1,maxv,it->l,it->r,Top-p);
			ans%=mod;ans+=mod;ans%=mod;
			int L=it->l,R=pre->r;
			S.erase(pre);
			it=S.lower_bound((node){0,x,0});
			S.erase(it);
			it=S.insert((node){L,R,Top}).fir;
			pre=it;pre++;
		}else{
			int to=w/sz,m=w%sz;w=0;
			seg::update(1,1,maxv,it->l,it->r,-to);
			if(m){
				ans-=qpow(3,p)*sz%mod;
				p-=to;sz-=m;
				ans+=qpow(3,p)*sz%mod;
				ans+=qpow(3,p-1)*m%mod;
				ans%=mod;ans+=mod;ans%=mod;
				int L=it->l,R=it->r;
				S.erase(it);
				seg::update(1,1,maxv,R-m+1,R,-1);
				S.insert((node){L,R-m,p});
				it=(S.insert((node){R-m+1,R,p-1})).fir;
			}else{
				ans-=qpow(3,p)*sz%mod;
				p-=to;
				int L=it->l,R=it->r;
				S.erase(it);
				it=(S.insert((node){L,R,p})).fir;
				ans+=qpow(3,p)*sz%mod;
				ans%=mod;ans+=mod;ans%=mod;
			}
		}
	}
}
signed main(){
	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	S.insert((node){0,0,(int)1e12});
	S.insert((node){1,(int)1e6,0});
	S.insert((node){(int)1e6+1,(int)1e6+1,0});
	cin>>D;
	for(int i=1;i<=D;i++){
		cin>>q[i].fir>>q[i].sec;
		modify(q[i].fir,q[i].sec);
		cout<<ans<<"\n";
	}
	return 0;
}
int D;
int qpow(int a,int b){
	b--;if(b==-1)return 0;
	int res=1;a%=mod;
	while(b){
		if(b&1)res=res*a%mod;
		a=a*a%mod;b>>=1;
	}return res;
}
pair <int,int> q[N];
pair <int,int> sta[N];int tot;
void solve(int n){
	int Max=0;
	vector <pair<int,int>> p;
	for(int i=1;i<=n;i++){
		if(i>1&&Max>(-q[i].sec))continue;
		Max=max(Max,-q[i].sec);
		p.push_back(mp(q[i].fir,-q[i].sec));
	}
	int ans=0;tot=0;
	sta[0]=mp(0,(int)1e12);
	for(int i=0;i<p.size();i++){
		int w=0;
		if(i==0){
			sta[++tot]=mp(p[i].fir,0ll);
			w=p[i].sec;
		}else{
			sta[++tot]=mp(p[i].fir-p[i-1].fir,0ll);
			w=p[i].sec-p[i-1].sec;
		}
		while(w){
			int Top=sta[tot-1].sec;
			if(w>=(Top-sta[tot].sec)*sta[tot].fir){
				w-=(Top-sta[tot].sec)*sta[tot].fir;
				ans-=qpow(3,sta[tot].sec)*sta[tot].fir%mod;
				ans+=qpow(3,Top)*sta[tot].fir%mod;
				ans%=mod;ans+=mod;ans%=mod;
				sta[tot-1].fir+=sta[tot].fir;
				tot--;
			}else{
				int to=w/sta[tot].fir,m=w%sta[tot].fir;w=0;
				if(m){
					ans-=qpow(3,sta[tot].sec)*sta[tot].fir%mod;
					sta[tot].sec+=to;sta[tot].fir-=m;
					ans+=qpow(3,sta[tot].sec)*sta[tot].fir%mod;
					sta[tot+1]=mp(m,sta[tot].sec+1);tot++;
					ans+=qpow(3,sta[tot].sec)*sta[tot].fir%mod;
					swap(sta[tot],sta[tot-1]);
					ans%=mod;ans+=mod;ans%=mod;
				}else{
					ans-=qpow(3,sta[tot].sec)*sta[tot].fir%mod;
					sta[tot].sec+=to;
					ans+=qpow(3,sta[tot].sec)*sta[tot].fir%mod;
					ans%=mod;ans+=mod;ans%=mod;
				}
			}
		}
		//cout<<p[i].fir<<" "<<p[i].sec<<"\n";
		//for(int j=1;j<=tot;j++)cout<<"("<<sta[j].fir<<","<<sta[j].sec<<") ";
		//cout<<"\n";	
	}
	cout<<ans<<"\n";
}
signed main(){
	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	cin>>D;
	for(int i=1;i<=D;i++){
		cin>>q[i].fir>>q[i].sec;
		q[i].sec=-q[i].sec;
		sort(q+1,q+1+i);
		solve(i);
	}
	return 0;
}
源文件, 语言: C++17

詳細信息 

answer.code:7:30: error: stray ‘#’ in program
    7 | const int N=2e5+10,mod=1e9+7;#include <bits/stdc++.h>
      |                              ^
answer.code:7:31: error: ‘include’ does not name a type
    7 | const int N=2e5+10,mod=1e9+7;#include <bits/stdc++.h>
      |                               ^~~~~~~
answer.code:13:11: error: redefinition of ‘const long long int N’
   13 | const int N=2e5+10,mod=1e9+7,maxv=1e6;
      |           ^
answer.code:7:11: note: ‘const long long int N’ previously defined here
    7 | const int N=2e5+10,mod=1e9+7;#include <bits/stdc++.h>
      |           ^
answer.code:13:20: error: redefinition of ‘const long long int mod’
   13 | const int N=2e5+10,mod=1e9+7,maxv=1e6;
      |                    ^~~
answer.code:7:20: note: ‘const long long int mod’ previously defined here
    7 | const int N=2e5+10,mod=1e9+7;#include <bits/stdc++.h>
      |                    ^~~
answer.code:185:5: error: redefinition of ‘long long int D’
  185 | int D;
      |     ^
answer.code:14:5: note: ‘long long int D’ previously declared here
   14 | int D;
      |     ^
answer.code:186:5: error: redefinition of ‘long long int qpow(long long int, long long int)’
  186 | int qpow(int a,int b){
      |     ^~~~
answer.code:15:5: note: ‘long long int qpow(long long int, long long int)’ previously defined here
   15 | int qpow(int a,int b){
      |     ^~~~
answer.code:194:16: error: redefinition of ‘std::pair<long long int, long long int> q [200010]’
  194 | pair <int,int> q[N];
      |                ^
answer.code:23:16: note: ‘std::pair<long long int, long long int> q [200010]’ previously defined here
   23 | pair <int,int> q[N];
      |                ^
answer.code:248:8: error: redefinition of ‘int main()’
  248 | signed main(){
      |        ^~~~
answer.code:172:8: note: ‘int main()’ previously defined here
  172 | signed main(){
      |        ^~~~
English 繁體中文 简体中文

伺服器時間: 2024-12-04 14:36:54 | 開源專案