QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#93794#6192. Interval ProblemksunhokimWA 155ms14168kbC++172.9kb2023-04-02 15:42:062023-04-02 15:42:10

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-04-02 15:42:10]
  • 评测
  • 测评结果:WA
  • 用时:155ms
  • 内存:14168kb
  • [2023-04-02 15:42:06]
  • 提交

answer

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

const int INF = 1e9;


#define dbg(x) "(" << #x <<": " << (x) << ") "
template<typename Ostream, typename Cont>
enable_if_t<is_same_v<Ostream,ostream>, Ostream&> 
operator<<(Ostream& os, const Cont& v){
	os<<"[";
	for(auto& x:v){os<<x<<", ";}
	return os<<"]";
}
template<typename ...Ts>
ostream& operator<<(ostream& os, const pair<Ts...>& p){
	return os<<"{"<<p.first<<", "<<p.second<<"}";
}

// Fenwick Tree for summation
struct fenwick_tree {
  int n;
  vector<ll> bits;
  fenwick_tree(int n) : n(n), bits(n+1) {}

  // add delta to node v
  void update(int v, int delta) {
    for (++v; v <= n; v += v&(-v)) 
      bits[v] += delta;
  }

  // get prefix sum of range [0,r]
  ll query(int r) {
    ll res = 0;
    for (++r; r > 0; r -= r&(-r))
      res += bits[r];
    return res;
  }
};

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);

  int n;
  cin >> n;
  
  vector<tuple<int,int,int>> intervals(n);
  vector<int> A(n*2);
  for (int i=0;i<n;i++){
    int l,r;
    cin >> l >> r;
    --l,--r;
    A[l] = i, A[r] = i;
    intervals[i]={l,r,i};
  }

  vector<ll> ans(n);
  vector<int> vis(n);
  fenwick_tree ft(n*2+1);
  sort(begin(intervals), end(intervals));
  for (int i=0;i<n;i++){
    auto [l,r,j] = intervals[i];
    ft.update(r,1);
  }
  for (int i=0;i<n;i++){
    auto [l,r,j] = intervals[i];
    ft.update(r,-1);
    ans[j] += ft.query(r) - ft.query(l);
  }
  for (int i=0;i<n;i++){
    auto [l,r,j] = intervals[i];
    ft.update(r,1);
  }
  for (int i=n-1;i>=0;i--){
    auto [l,r,j] = intervals[i];
    ft.update(r,-1);
    ans[j] -= ft.query(2*n) - ft.query(r);
  }


  auto calc = [&](vector<int>& order, bool inv) {
    map<int, int> stack;
    set<int> indices;
    map<int, int> zombies;
    ll kill_sum = 0;
    int kill = 0;
    for (int i : order) {
      // cout << dbg(i) dbg(A[i]) dbg(kill_sum) dbg(kill) dbg(zombies.size())<< "\n";
      if (!stack.count(A[i])) {
        stack.insert({A[i],i});
        indices.insert(inv ? -i : i);
        ans[A[i]] += 2*zombies.size() + kill + kill_sum;
      } else {
        indices.erase(inv ? -stack[A[i]] : stack[A[i]]);
        zombies.insert({inv ? -i : i, A[i]});
        stack.erase(A[i]);
        ans[A[i]] += stack.size();
        if (stack.empty()) {
          kill = 0;
          kill_sum = 0;
        } else {
          for (auto it = zombies.begin(); it != zombies.end();) {
            if (it->first < *indices.begin()) {
              it = zombies.erase(it);
              kill++;
              kill_sum += 1;
            } else {
              break;
            }
          }
        }
      }
    }
  };
  vector<int> order(2*n);
  iota(begin(order), end(order), 0);
  calc(order, false);
  reverse(begin(order), end(order));
  calc(order, true);


  for (int i=0;i<n;i++){
    cout << ans[i] << "\n";
  }
}

詳細信息

Test #1:

score: 100
Accepted
time: 2ms
memory: 3336kb

input:

5
2 3
6 7
1 9
5 10
4 8

output:

7
5
4
5
5

result:

ok 5 number(s): "7 5 4 5 5"

Test #2:

score: -100
Wrong Answer
time: 155ms
memory: 14168kb

input:

200000
342504 342505
248314 248317
259328 259334
234817 234821
225726 225732
371424 371425
260562 260565
34752 34753
132098 132100
262130 262134
7254 7255
228491 228492
43488 43492
188408 188410
11691 11692
350334 350335
327350 327352
360684 360685
182051 182052
72131 72135
194666 194668
61303 61313...

output:

23
38
25
24
24
31
18
17
19
29
23
14
33
42
26
23
12
25
30
20
16
40
12
17
18
12
38
34
30
20
22
8
36
23
32
25
29
20
31
25
15
26
26
27
18
9
12
38
38
27
38
28
20
24
16
30
18
14
45
28
12
32
16
25
28
30
30
24
10
30
16
39
23
18
15
16
56
19
13
25
15
22
15
35
15
33
30
28
33
38
18
20
33
38
9
10
32
12
8
15
18
1...

result:

wrong answer 1st numbers differ - expected: '12', found: '23'