oj.uz

답안 #491288

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
491288 2021-12-01T11:18:28 Z Wayne_Yan Meteors (POI11_met) C++17
0 / 100
 6000 ms 65540 KB 
#include <bits/extc++.h>
using namespace std;
using namespace __gnu_pbds;
#define int long long
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;

struct BIT{
  int arr[maxN];
  void modify(int c, int diff){
    if(c == 0) return;
    while(c < maxN){
      arr[c] += diff;
      c += (c&-c);
    }
  }
  int query(int c){
    int ans = 0;
    while(c){
      ans += arr[c];
      c -= (c&-c);
    }
    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 N,M,K;
const int maxC = 1e9;
int O[maxN];
int L[maxN], R[maxN], C[maxN];
int T[maxN];
int ans[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;

  int got[maxN] = {};

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

  bool flag[maxN] = {};

  for(int i : lands){
    if(got[O[i]] >= T[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]);
    }
  }

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


}

signed main(){
  
  cin >> N >> M;
  F(M){
    cin >> O[i+1];
  }
  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(ans[i] == K+1){
      printf("NIE\n");
    }else{
      printf("%lld\n", ans[i]);
    }
  }

  return 0;
}

Subtask #1
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 164 ms 31836 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 163 ms 31944 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 6057 ms 61040 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 6055 ms 59996 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 6063 ms 60512 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 6087 ms 59972 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #7
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 468 ms 65540 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #8
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 481 ms 65540 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -