Submission #1115983

#	Time	Username	Problem	Language	Result	Execution time	Memory
1115983		EfeBabagil	Trains (BOI24_trains)	C++14	0 / 100	33 ms	4228 KiB

Main

#include<bits/stdc++.h>
using namespace std;
#define int long long
long long INF=1e17;
const int N=4e6+1;
int mod=1e9+7;
int tree[N];
int lazy[N];
int a[N];
int n;
#define mid (start+end)/2
void push(int node, int start, int end)
{
	if(!lazy[node])
		return;
	if(start!=end){
		lazy[node*2]+=lazy[node];
		lazy[node*2+1]+=lazy[node];
	}
	tree[node]+=lazy[node]*(end-start+1);
	lazy[node]=0;
}
void build(int node,int start,int end)  
{  
	if(start==end)
	{
		tree[node]=a[start];
		return;
	}
	build(node*2,start,mid);
	build(node*2+1,mid+1,end);
	tree[node]=tree[node*2+1]+tree[node*2];
}
int query(int node, int start, int end, int l, int r)
{
	if(start>r || end<l) return 0;
	push(node,start,end);
	if(start>=l && end<=r)
	{
		return tree[node];
	}
	return query(node*2,start,mid,l,r)+query(node*2+1,mid+1,end,l,r);
	
}
void update(int node, int start, int end, int l, int r, int val)  
{  
	if(start>r || end<l) return;
	if(start>=l && end<=r)
	{
		lazy[node]+=val;
		push(node,start,end);
		return;
	}
	update(node*2,start,mid,l,r,val);
	update(node*2+1,mid+1,end,l,r,val);
	tree[node]=tree[node*2+1]+tree[node*2];
	
} 
int32_t main()
{
	  
    int q;
    int n;
    cin>>n;
    vector<pair<int,int>> city(n);
    q=n;
    
    a[1]=1;
    build(1,1,n);
    int i=1;
    int ans=0;
	while(i<=q)
	{
		int type;
		int a,b;
        cin>>a>>b;
        
		int z=query(1,1,n,i,i);
		ans=(ans+z)%mod;
	
		update(1,1,n,min(i+1,n),min(n,i+b),z);
		i++;
	}
    cout<<ans<<endl;
    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int32_t main()':
Main.cpp:74:7: warning: unused variable 'type' [-Wunused-variable]
   74 |   int type;
      |       ^~~~

• Subtask 1: 0 / 8
• Subtask 2: 0 / 13
• Subtask 3: 0 / 16
• Subtask 4: 0 / 34
• Subtask 5: 0 / 29