题解：AT_arc210_a [ARC210A] Always Increasing

#include <iostream>
#include <stdio.h>
#include <queue>
#define int long long 
#define add(u,v,z) to[++ tot] = v,w[tot] = z,nxt[tot] = h[u],h[u] = tot
#define con putchar_unlocked(' ')
#define ent putchar_unlocked('\n')
#define Blue_Archive return 0
using namespace std;
constexpr int N = 2e5 + 3;
constexpr int M = 1e6 + 3;
constexpr int INF = 1e9;

int T;
int n;
int m;
int ans;
int tot;
int h[N];
int w[M];
int to[M];
int nxt[M];
int dis[N];
int cnt[N];
int laz[N];

bool vis[N];

queue<int> q;

inline int read()
{
	int x = 0,f = 1;
	int c = getchar_unlocked();
	while(c < '0' || c > '9') f = (c == '-' ? -1 : f),c = getchar_unlocked();
	while(c >= '0' && c <= '9') x = (x << 1) + (x << 3) + (c ^ 48),c = getchar_unlocked();
	return x * f;
}

inline void write(int x)
{
	if(x < 0) x = -x,putchar_unlocked('-');
	if(x > 9) write(x / 10);
	putchar_unlocked(x % 10 + '0');
}

inline bool spfa()
{
	for(int i = 1;i <= n + 1;i ++) dis[i] = INF,cnt[i] = 0;
	dis[n + 1] = 0;
	q.push(n + 1);
	while(!q.empty())
	{
		int u = q.front();
		q.pop();
		if(cnt[u] > n) return 0;
		cnt[u] ++;
		for(int i = h[u];i;i = nxt[i])	
		{
			if(dis[to[i]] > dis[u] + w[i])
			{
				dis[to[i]] = dis[u] + w[i];
				q.push(to[i]);
			}
		}
	}
	return 1;
}

signed main()
{
	#ifndef ONLINE_JUDGE
		freopen("data.in","r",stdin);freopen("data.out","w",stdout);
	#endif
	n = read();
	m = read();
	for(int i = 1;i < n;i ++) add(i + 1,i,-1);
	for(int i = 1,pos,val;i <= m;i ++)
	{
		pos = read();
		val = read();
		laz[pos] += val;
		if(pos < n) add(pos + 1,pos,-laz[pos] + laz[pos + 1] - 1);
	}
	for(int i = 1;i <= n;i ++) add(n + 1,i,0);
	spfa();
	int mx = INF;
	for(int i = 1;i <= n;i ++) mx = min(mx,dis[i]);
	for(int i = 1;i <= n;i ++) ans += dis[i] - mx + 1;
	write(ans);ent;
	Blue_Archive;
}