Submission #1105076

#	Time	Username	Problem	Language	Result	Execution time	Memory
1105076		VinhLuu	Remittance (JOI19_remittance)	C++17	0 / 100	2 ms	6788 KiB

remittance

#include <bits/stdc++.h>
//#define int long long
#define ll long long
using namespace std;

const int N = 1e6 + 5;
const int oo = 1e9;


int c[N], n, a[N], b[N];
bool f[N];

int st[N << 1];

void update(int i){
  i += n - 1;
  while(i > 1){
    i /= 2;
    if(c[st[i << 1]] >= c[st[i << 1|1]]) st[i] = st[i << 1];
    else st[i] = st[i << 1|1];
  }
}

signed main(){
  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  #define task "v"
  if(fopen(task ".inp","r")){
    freopen(task ".inp","r",stdin);
    freopen(task ".out","w",stdout);
  }
  cin >> n;
  for(int i = 1; i <= n; i ++){
    cin >> a[i] >> b[i];
    c[i] = a[i] - b[i];
    st[i + n - 1] = i;
  }

  for(int i = n - 1; i >= 1; i --){
    if(c[st[i << 1]] >= c[st[i << 1|1]]) st[i] = st[i << 1];
    else st[i] = st[i << 1|1];
  }
  while(true){
    if(c[st[1]] <= 1) break;
//    cerr << st[1] << " " << c[st[1]] << " k\n";
    int nx = (st[1] == n ? 1 : st[1] + 1);
    int val = c[st[1]] / 2;
    c[nx] += val;
    c[st[1]] -= val * 2;
    update(nx);
    update(st[1]);
  }
  bool ff = true, gg = true, vv = true;
  for(int i = 1; i <= n; i ++){
    if(c[i] < 0){
      cout << "No\n";
      return 0;
    }
    if(c[i] != 0) ff = false;
    if(c[i] == 0) vv = false;
    if(c[i] + b[i] > 1) gg = false;
  }
  if(ff){
    cout << "Yes\n";
    return 0;
  }

  if(!gg && vv){
    cout << "Yes\n";
  }else cout << "No\n";

}

Compilation message (stderr)

remittance.cpp: In function 'int main()':
remittance.cpp:28:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   28 |     freopen(task ".inp","r",stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
remittance.cpp:29:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   29 |     freopen(task ".out","w",stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 15
• Subtask 2: 0 / 40
• Subtask 3: 0 / 45