oj.uz

Submission #491298

# Submission time Handle Problem Language Result Execution time Memory
491298 2021-12-01T12:21:34 Z Wayne_Yan Meteors (POI11_met) C++17
100 / 100
 1168 ms 52604 KB 
#include <bits/extc++.h>
using namespace std;
using namespace __gnu_pbds;
typedef int64_t ll;
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)
#define debug(x) (cerr << (#x) << " = " << x << "\n")

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>;

const int maxN = 3e5+10;
const int maxC = 1e9;

struct BIT{
  long long arr[maxN];
  void modify(int c, int diff){
    if(c == 0) return;
    assert(c > 0);
    while(c < maxN){
      arr[c] += diff;
      c += (c&-c);
    }
  }
  int query(int c){
    assert(c > 0);
    long long ans = 0;
    while(c){
      ans += arr[c];
      c -= (c&-c);
    }
    if(ans > maxC) ans = maxC;
    return ans;
  }

  void modify(int ql, int qr, int diff){
    modify(qr+1, -diff);
    modify(ql, diff);
  }
  BIT () {fill(arr, arr+maxN, 0);}
} bit;


int got[maxN];
int N,M,K;
int O[maxN];
int L[maxN], R[maxN], C[maxN];
int T[maxN];
int ans[maxN];
bool flag[maxN];


void solve(vector<int> lands, int ql, int qr){
  
  if(ql + 1 == qr){
    for(int i : lands){
      ans[O[i]] = ql;
    }
    return;
  }
  

  int qm = (ql+qr) >> 1;
  Fl(i, ql, qm){
    if(L[i] <= R[i]){
      bit.modify(L[i], R[i], C[i]);
    }else{
      bit.modify(L[i], M, C[i]);
      bit.modify(1, R[i], C[i]);
    }
  }
  
  vector<int> llands, rlands;


  for(int i : lands){
    got[O[i]] += bit.query(i);
    if(got[O[i]] >= maxC) got[O[i]] = maxC;
  }


  for(int i : lands){
    if(got[O[i]] >= T[O[i]] && (!flag[O[i]])){
      llands.pb(i);
    }else{
      rlands.pb(i);
      if(!flag[O[i]]){
        flag[O[i]] = true;
        T[O[i]] -= got[O[i]];
      }
    }
  }


  Fl(i, ql, qm){
    if(L[i] <= R[i]){
      bit.modify(L[i], R[i], -C[i]);
    }else{
      bit.modify(L[i], M, -C[i]);
      bit.modify(1, R[i], -C[i]);
    }
  }

  for(int i : lands){
    got[O[i]] = 0;
    flag[O[i]] = 0;
  }

  solve(llands, ql, qm);
  solve(rlands, qm, qr);


}

signed main(){
  
  cin >> N >> M;
  bool covered[maxN] = {};
  F(M){
    cin >> O[i+1];
    covered[O[i+1]] = true;
  }
  F(N){
    cin >> T[i+1];
  }
  cin >> K;
  F(K){
    cin >> L[i+1] >> R[i+1] >> C[i+1];
  }
  L[0] = 1;
  R[0] = M;
  C[0] = 0;
  L[K+1] = 1;
  R[K+1] = M;
  C[K+1] = 1e9;

  vector<int> orig;
  Fl(i, 1, M+1){
    orig.pb(i);
  }
  
  solve(orig, 0, K+2); 

  Fl(i, 1, N+1){
    if(covered[i] == false && T[i]){
      printf("NIE\n");
    }else if(ans[i] == K+1){
      printf("NIE\n");
    }else{
      printf("%d\n", ans[i]);
    }
  }

  return 0;
}

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 3020 KB Output is correct
2 Correct 6 ms 3020 KB Output is correct
3 Correct 4 ms 2996 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 3020 KB Output is correct
2 Correct 3 ms 3020 KB Output is correct
3 Correct 5 ms 3020 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 98 ms 8800 KB Output is correct
2 Correct 176 ms 10772 KB Output is correct
3 Correct 153 ms 6388 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 160 ms 5356 KB Output is correct
2 Correct 149 ms 5316 KB Output is correct
3 Correct 172 ms 8632 KB Output is correct
4 Correct 42 ms 7360 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 123 ms 6236 KB Output is correct
2 Correct 165 ms 9012 KB Output is correct
3 Correct 134 ms 3572 KB Output is correct
4 Correct 131 ms 5720 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 154 ms 8208 KB Output is correct
2 Correct 195 ms 8128 KB Output is correct
3 Correct 114 ms 6912 KB Output is correct
4 Correct 163 ms 7840 KB Output is correct

Subtask #7
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1000 ms 39112 KB Output is correct
2 Correct 854 ms 52604 KB Output is correct
3 Correct 751 ms 5980 KB Output is correct
4 Correct 1168 ms 17772 KB Output is correct

Subtask #8
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1000 ms 33484 KB Output is correct
2 Correct 871 ms 27220 KB Output is correct
3 Correct 627 ms 5376 KB Output is correct
4 Correct 1136 ms 21152 KB Output is correct