結果
問題 | No.1290 Addition and Subtraction Operation |
ユーザー |
![]() |
提出日時 | 2020-11-13 22:39:59 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 13 ms / 2,000 ms |
コード長 | 4,906 bytes |
コンパイル時間 | 2,518 ms |
コンパイル使用メモリ | 212,528 KB |
最終ジャッジ日時 | 2025-01-15 23:39:36 |
ジャッジサーバーID (参考情報) |
judge1 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 85 |
ソースコード
#pragma GCC optimize ("Ofast")#include<bits/stdc++.h>using namespace std;void*wmem;char memarr[96000000];template<class T> inline void walloc1d(T **arr, int x, void **mem = &wmem){static int skip[16] = {0, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1};(*mem) = (void*)( ((char*)(*mem)) + skip[((unsigned long long)(*mem)) & 15] );(*arr)=(T*)(*mem);(*mem)=((*arr)+x);}template<class T> inline void walloc1d(T **arr, int x1, int x2, void **mem = &wmem){walloc1d(arr, x2-x1, mem);(*arr) -= x1;}inline int my_getchar_unlocked(){static char buf[1048576];static int s = 1048576;static int e = 1048576;if(s == e && e == 1048576){e = fread_unlocked(buf, 1, 1048576, stdin);s = 0;}if(s == e){return EOF;}return buf[s++];}inline void rd(int &x){int k;int m=0;x=0;for(;;){k = my_getchar_unlocked();if(k=='-'){m=1;break;}if('0'<=k&&k<='9'){x=k-'0';break;}}for(;;){k = my_getchar_unlocked();if(k<'0'||k>'9'){break;}x=x*10+k-'0';}if(m){x=-x;}}inline void rd(long long &x){int k;int m=0;x=0;for(;;){k = my_getchar_unlocked();if(k=='-'){m=1;break;}if('0'<=k&&k<='9'){x=k-'0';break;}}for(;;){k = my_getchar_unlocked();if(k<'0'||k>'9'){break;}x=x*10+k-'0';}if(m){x=-x;}}struct MY_WRITER{char buf[1048576];int s;int e;MY_WRITER(){s = 0;e = 1048576;}~MY_WRITER(){if(s){fwrite_unlocked(buf, 1, s, stdout);}}};MY_WRITER MY_WRITER_VAR;void my_putchar_unlocked(int a){if(MY_WRITER_VAR.s == MY_WRITER_VAR.e){fwrite_unlocked(MY_WRITER_VAR.buf, 1, MY_WRITER_VAR.s, stdout);MY_WRITER_VAR.s = 0;}MY_WRITER_VAR.buf[MY_WRITER_VAR.s++] = a;}inline void wt_L(char a){my_putchar_unlocked(a);}inline void wt_L(const char c[]){int i=0;for(i=0;c[i]!='\0';i++){my_putchar_unlocked(c[i]);}}struct unionFind{int*d;int N;int M;inline void malloc(const int n){d = (int*)std::malloc(n*sizeof(int));M = n;}inline void malloc(const int n, const int fg){d = (int*)std::malloc(n*sizeof(int));M = n;if(fg){init(n);}}inline void free(void){std::free(d);}inline void walloc(const int n, void **mem=&wmem){walloc1d(&d, n, mem);M = n;}inline void walloc(const int n, const int fg, void **mem=&wmem){walloc1d(&d, n, mem);M = n;if(fg){init(n);}}inline void init(const int n){int i;N = n;for(i=(0);i<(n);i++){d[i] = -1;}}inline void init(void){init(M);}inline int get(int a){int t = a;int k;while(d[t]>=0){t=d[t];}while(d[a]>=0){k=d[a];d[a]=t;a=k;}return a;}inline int connect(int a, int b){if(d[a]>=0){a=get(a);}if(d[b]>=0){b=get(b);}if(a==b){return 0;}if(d[a] < d[b]){d[a] += d[b];d[b] = a;}else{d[b] += d[a];d[a] = b;}return 1;}inline int operator()(int a){return get(a);}inline int operator()(int a, int b){return connect(a,b);}inline int& operator[](const int a){return d[a];}inline int size(int a){a = get(a);return -d[a];}inline int sizeList(int res[]){int i;int sz=0;for(i=(0);i<(N);i++){if(d[i]<0){res[sz++] = -d[i];}}return sz;}};int N;int M;int L[100000];int R[100000];long long A[100000];long long x[100000+2];long long sm[100000+2];int main(){int i;wmem = memarr;unionFind uf;rd(N);rd(M);{int Lj4PdHRW;for(Lj4PdHRW=(0);Lj4PdHRW<(N);Lj4PdHRW++){rd(A[Lj4PdHRW]);}}{int e98WHCEY;for(e98WHCEY=(0);e98WHCEY<(M);e98WHCEY++){rd(L[e98WHCEY]);L[e98WHCEY] += (-1);rd(R[e98WHCEY]);}}for(i=(1);i<(N);i+=(2)){A[i] *= -1;}x[0] = A[0];for(i=(1);i<(N);i++){x[i] = A[i] - A[i-1];}x[N] = -A[N-1];uf.walloc(N+1,1);for(i=(0);i<(M);i++){uf(L[i], R[i]);}for(i=(0);i<(N+1);i++){sm[uf(i)] += x[i];}for(i=(0);i<(N+1);i++){if(sm[i]){wt_L("NO");wt_L('\n');return 0;}}wt_L("YES");wt_L('\n');return 0;}// cLay varsion 20201102-1// --- original code ---// int N, M, L[1d5], R[1d5];// ll A[1d5];// ll x[1d5+2], sm[1d5+2];// {// unionFind uf;// rd(N,M,A(N),(L--,R)(M));// rep(i,1,N,2) A[i] *= -1;//// x[0] = A[0];// rep(i,1,N) x[i] = A[i] - A[i-1];// x[N] = -A[N-1];//// uf.walloc(N+1,1);// rep(i,M) uf(L[i], R[i]);// rep(i,N+1) sm[uf(i)] += x[i];// rep(i,N+1) if(sm[i]) wt("NO"), return 0;// wt("YES");// }