結果
問題 |
No.1290 Addition and Subtraction Operation
|
ユーザー |
![]() |
提出日時 | 2020-11-22 23:39:55 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 33 ms / 2,000 ms |
コード長 | 1,698 bytes |
コンパイル時間 | 943 ms |
コンパイル使用メモリ | 88,052 KB |
実行使用メモリ | 6,948 KB |
最終ジャッジ日時 | 2024-07-23 16:48:50 |
合計ジャッジ時間 | 5,767 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 85 |
ソースコード
#include <iostream> #include <algorithm> #include <iomanip> #include <vector> #include <queue> #include <set> #include <map> using namespace std; typedef long long ll; struct UnionFind { vector<int> data; UnionFind(int size) : data(size, -1) {} bool unionSet(int x, int y) { x = root(x); y = root(y); if (x != y) { if (data[y] < data[x]) swap(x, y); data[x] += data[y]; data[y] = x; } return x != y; } bool findSet(int x, int y) { return root(x) == root(y); } int root(int x) { return data[x] < 0 ? x : data[x] = root(data[x]); } int size(int x) { return -data[root(x)]; } }; int n, m; ll b[100000]; ll dif[100000]; int l[100000], r[100000]; void input(){ cin >> n >> m; for(int i = 0; i < n; i++){ cin >> b[i]; if(i%2 == 1) b[i] *= -1; } for(int i = 0; i < m; i++){ cin >> l[i] >> r[i]; l[i]--; r[i]--; } dif[0] = b[0]; dif[n] = -b[n-1]; for(int i = 1; i < n; i++){ dif[i] = b[i]-b[i-1]; } } void solve(){ UnionFind uf(n+1); for(int i = 0; i < m; i++){ uf.unionSet(l[i], r[i]+1); } vector<ll> root_sum(n+1); for(int i = 0; i <= n; i++){ int r = uf.root(i); root_sum[r] += dif[i]; } // for(int i = 0; i <= n; i++) cout << root_sum[i] << ' '; // cout << endl; for(int i = 0; i <= n; i++){ if(root_sum[i] != 0){ cout << "NO" << endl; return; } } cout << "YES" << endl; } int main(){ ios::sync_with_stdio(false); cin.tie(0); cout << setprecision(10) << fixed; input(); solve(); }