Submission #1116039

#	Time	Username	Problem	Language	Result	Execution time	Memory
1116039		EfeBabagil	Trains (BOI24_trains)	C++14	16 / 100	80 ms	8168 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*2]+lazy[node])%mod;
		lazy[node*2+1]=(lazy[node*2+1]+lazy[node])%mod;
	}
	tree[node]+=(lazy[node]*(end-start+1))%mod;
	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))%mod;
	
}
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]=(lazy[node]+val)%mod;
		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])%mod;
	
} 
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))%mod;
		ans=(ans+z)%mod;
	    if(i<n)
		update(1,1,n,i+1,min(n,i+b),z);
		i++;
	}
    cout<<ans<<endl;
    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int32_t main()':
Main.cpp:80:6: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   80 |      if(i<n)
      |      ^~
Main.cpp:82:3: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   82 |   i++;
      |   ^
Main.cpp:74:7: warning: unused variable 'type' [-Wunused-variable]
   74 |   int type;
      |       ^~~~

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