Submission #1241513

#TimeUsernameProblemLanguageResultExecution timeMemory
1241513trantrungkeinRemittance (JOI19_remittance)C++20
100 / 100
343 ms48284 KiB
#include <bits/stdc++.h>
 #define int long long 
#define fi           first 
#define si           second 
#define For(i,a,b)   for (int i = (a), _b =(b); i <= _b; ++i)
#define all(v)       v.begin(), v.end()
#define Unique(v)    v.erase(unique(all(v)), v.end())   
#define MASK(i)      (1LL << (i))
#define bit(i,n)     (((n)>>(i)) & 1)
#define Vii          vector<pair<int,int>>
#define setpr(x)     cout<<setprecision(x)<<fixed
#define Prior        priority_queue< pair<int,int> , Vii, greater<Pair> >
using namespace std;
 
const int Mod = 1E9 + 7;
const long long INF  = 4E18;
const int N = 1e6 + 1;
struct node
{
    int id,value,val;
    // bool operator < (const node & other) const
    // {
    //     return val < other.val;
    // }
};
queue<node> q;
int n,a[N],b[N],curr[N];
signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0); 
    cin >> n;
    For(i,1,n)
    {
        cin >> a[i] >> b[i];
        curr[i] = a[i];
        if(a[i] > b[i])
        {   
            if((a[i]-b[i])%2==0) q.push({i,a[i],a[i]-b[i]});
            else if(b[i] != 0)
            {   
                q.push({i,a[i],a[i]-b[i]+1});
            }
        }
    }
    while(!q.empty())
    {
        auto [id,value,diff] = q.front();q.pop();
        if(curr[id] != value) continue;
        int nxt = id + 1;
        if(nxt > n) nxt = 1;
        curr[nxt] += (diff/2);
        curr[id] -= diff;
        if(curr[nxt] > b[nxt])
        {
            if((curr[nxt] - b[nxt])%2==0) q.push({nxt,curr[nxt],curr[nxt] - b[nxt]});
            else if(b[nxt] != 0)
            {
                q.push({nxt,curr[nxt],curr[nxt] - b[nxt] + 1});
            }
        }       
    }
    For(i,1,n)
    {   
        if(curr[i] != b[i]) 
        {
            cout << "No"; return 0;
        }
    }
    cout << "Yes";
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...