Submission #491249

#	Time	Username	Problem	Language	Result	Execution time	Memory
491249		Wayne_Yan	새로운 문제 (POI11_met)	C++17	0 / 100	1198 ms	65540 KiB

met

#include <bits/extc++.h>
using namespace std;
using namespace __gnu_pbds;

typedef long double ld;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define pb emplace_back
#define mp make_pair
#define mt make_tuple
#define pii pair<int,int>
#define F(n) Fi(i,n)
#define Fi(i,n) Fl(i,0,n)
#define Fl(i,l,n) for(int i=l;i<n;i++)
#define RF(n) RFi(i,n)
#define RFi(i,n) RFl(i,0,n)
#define RFl(i,l,n) for(int i=n-1;i>=l;i--)
#define all(v) begin(v),end(v)
#define siz(v) (ll(v.size()))
#define get_pos(v,x) (lower_bound(all(v),x)-begin(v))
#define sort_uni(v) sort(begin(v),end(v)),v.erase(unique(begin(v),end(v)),end(v))
#define mem(v,x) memset(v,x,sizeof v)
#define ff first
#define ss second
#define mid ((l+r)>>1)
#define RAN(a,b) uniform_int_distribution<int> (a, b)(rng)

template <typename T> using max_heap = __gnu_pbds::priority_queue<T,less<T> >;
template <typename T> using min_heap = __gnu_pbds::priority_queue<T,greater<T> >;
template <typename T> using rbt = tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;

struct meteor{
  int l,r,a;
  meteor(int ll, int rr, int aa) : l(ll), r(rr), a(aa) {}
  meteor() {}
};

int N;

const int maxN = 3e5+10;
int segment[4*maxN], lazy[4*maxN];

void pull(int t){
  if(2*t+1 < 4*maxN){
    segment[t] = max(segment[2*t], segment[2*t+1]);
  }
}

void push(int t){
  if(2*t+1 >= 4*maxN) return;
  if(lazy[t]){
    segment[2*t] += lazy[t];
    segment[2*t+1] += lazy[t];
    lazy[2*t] += lazy[t];
    lazy[2*t+1] += lazy[t];
    lazy[t] = 0;
  }
}

void modify(int ql, int qr, int c, int l = 0, int r = maxN, int idx = 1){
  if(ql >= r || qr <= l) return;
  push(idx);
  if(ql <= l && qr >= r){
    segment[idx] += c;
    lazy[idx] += c;
    return;
  }
  modify(ql, qr, c, l, mid, 2*idx);
  modify(ql, qr, c, mid, r, 2*idx+1);
  pull(idx);
}

int query(int ql, int qr, int l = 0, int r = maxN, int idx = 1){
  if(ql >= r || qr <= l) return 0;
  push(idx);
  if(ql <= l && qr >= r){
    return segment[idx];
  }
  return max(query(ql, qr, l, mid, 2*idx), query(ql, qr, mid, r, 2*idx+1)) ;
}

vector<int> solve(vector<int> landlord, vector<int> owner, vector<int> target, vector<meteor> shower){
  int n = (int)landlord.size();
  int k = (int)shower.size();
  int m = (int)owner.size();

  vector<int> returning(N+1, 0);
  if(n == 0) return returning;
  if(k == 1){
    for(int i : landlord){
      returning[i] = 1;
    }
    return returning;
  }

  F(k/2){
    meteor curr = shower[i];
    if(curr.l > curr.r){
      modify(0, curr.r+1, curr.a);
      modify(curr.l, m, curr.a);
    }else{
      modify(curr.l, curr.r+1, curr.a);
    }
  }

  vector<int> got(N, 0);
  vector<int> owning[N];

  F(m){
    int c = query(i, i+1);
    got[owner[i]] += c;
    owning[owner[i]].pb(i);
  }

  vector<int> lland, rland; // left lands and right lands
  vector<int> llandlord, rlandlord;
  vector<int> ltarget(N, 0);
  vector<int> rtarget(N, 0);
  // split landlords

  for(int i : landlord){
    if(got[i] >= target[i]){
      for(int j : owning[i]){
        lland.pb(j);
      }
      llandlord.pb(i);
      ltarget[i] = target[i];
    }else{
      for(int j : owning[i]){
        rland.pb(j);
      }
      rlandlord.pb(i);
      rtarget[i] = target[i] - got[i];
    }
  }

  sort(all(lland));
  sort(all(rland));

  vector<int> lowner, rowner;
  for(int i : lland){
    lowner.pb(owner[i]);
  }
  for(int i : rland){
    rowner.pb(owner[i]);
  }

  // split queries

  vector<meteor> lquery;
  vector<meteor> rquery;

  F(k){
    if(i < k/2){
      meteor curr = shower[i];
      if(curr.l <= curr.r){
        curr.l = (int)get_pos(lland, curr.l);
        curr.r++;
        curr.r = (int)get_pos(lland, curr.r);
        curr.r--;
      }else{
        curr.r = (int)get_pos(lland, curr.r);
        curr.l++;
        curr.l = (int)get_pos(lland, curr.l);
        curr.l--;
      }
      lquery.pb(curr);
    }else{
      meteor curr = shower[i];
      if(curr.l <= curr.r){
        curr.l = (int)get_pos(rland, curr.l);
        curr.r++;
        curr.r = (int)get_pos(rland, curr.r);
        curr.r--;
      }else{
        curr.r = (int)get_pos(rland, curr.r);
        curr.l++;
        curr.l = (int)get_pos(rland, curr.l);
        curr.l--;
      }
      rquery.pb(curr);
    }
  }

  // reset queries
  F(k/2){
    meteor curr = shower[i];
    if(curr.l > curr.r){
      modify(1, curr.r+1, -curr.a);
      modify(curr.l, m+1, -curr.a);
    }else{
      modify(curr.l, curr.r+1, -curr.a);
    }
  }

  //solve ...
  //solve ...
  
  vector<int> lans = solve(llandlord, lowner,ltarget, lquery);
  vector<int> rans = solve(rlandlord, rowner,rtarget, rquery);
  
  for(int i : llandlord){
    returning[i] = lans[i];
  }
  for(int i : rlandlord){
    returning[i] = rans[i] + k/2;
  }

  return returning;
}

signed main(){
  
  int m; // n: landlord, m: pieces of land
  cin >> N >> m;
  vector<int> owner(m);
  vector<int> target(N);
  F(m) cin >> owner[i], owner[i]--;
  F(N) cin >> target[i];
  int k;
  cin >> k;
  vector<meteor> showers(k);
  F(k){
    int a,b,c;
    cin >> a >> b >> c;
    showers[i].l = a-1;
    showers[i].r = b-1;
    showers[i].a = c;
  }
  meteor bruh(1, m, 1000000000);
  showers.pb(bruh);
  vector<int> orig;
  F(N) orig.pb(i);

  vector<int> res;
  res = solve(orig, owner, target, showers);
  
  
  
  for(int i : orig){
    res[i]--;
    if(res[i] == k){
      printf("NIE\n");
    }else{
      printf("%d\n", res[i]+1);
    }
  }
  
  return 0;
} 

• Subtask 1: 0 / 12
• Subtask 2: 0 / 12
• Subtask 3: 0 / 12
• Subtask 4: 0 / 12
• Subtask 5: 0 / 13
• Subtask 6: 0 / 13
• Subtask 7: 0 / 13
• Subtask 8: 0 / 13