QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#877755#9765. Repetitive Routesemersonjr02AC ✓0ms3584kbC++172.9kb2025-02-01 03:13:322025-02-01 03:13:32

Judging History

This is the latest submission verdict.

  • [2025-02-01 03:13:32]
  • Judged
  • Verdict: AC
  • Time: 0ms
  • Memory: 3584kb
  • [2025-02-01 03:13:32]
  • Submitted

answer

#include <bits/stdc++.h>
 
using namespace std;
 
#define int long long
#define ll long long
#define endl "\n"
#define F first
#define S second
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define rep(i, a, b) for(int i = a; i < b; i++)
#define tam(s) (int)s.size()
#define all(x) x.begin(), x.end()
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
 
typedef vector<int> vi;
typedef pair<int, int> pii;
typedef tuple<int, int, int> tii;
constexpr int oo=((unsigned int)(-1) >> 1), mod=1e9+7;
vector<pii> dirs = {{1,0}, {-1, 0}, {0, 1}, {0, -1}};
 
int log2_ceil(unsigned long long i){
    int ans = (i ? (__builtin_clzll(1) - __builtin_clzll(i)) : -1);
    if(ans > 0 && (1ULL << ans) ^ i) ans++;
    return ans; 
}
 
struct Segtree{
    
    int size;
    vector<int> tree, range;
    vector<vi> next;
 
    Segtree(int n){
        size = 1 << log2_ceil(n);
        tree.assign(2*size, 0LL);
        next.resize(2*size);
        range.resize(2*size);
        rep(i, size, 2*size) range[i] = i-size;
        for(int i=size-1; i > 0; i--) range[i] = range[i*2+1];
    }
 
    void build() {
        for(int i=size-1; i > 0; i--){ 
            tree[i] = tree[i*2] + tree[i*2+1];
            int j, k;
            for(j=0, k=0; j < tam(next[i*2]) && k < tam(next[i*2+1]);){
                if(next[i*2][j] <= range[i*2+1]) tree[i]--, j++;
                else if(next[i*2][j] < next[i*2+1][k]) next[i].pb(next[i*2][j]), j++;
                else next[i].pb(next[i*2+1][k]), k++;
            }
            while(j < tam(next[i*2])) next[i].pb(next[i*2][j]), j++;
            while(k < tam(next[i*2+1])) next[i].pb(next[i*2+1][k]), k++;
        }
    }
 
    int query(int l, int r) {
        int s = 0, ir=r, i;
        l += size; r += size;
        while (l <= r) {
            if (l%2 == 1){ 
                s += tree[l];
                i = upper_bound(all(next[l]), ir+size) - next[l].begin();
                s -= i; l++;
            }
            if (r%2 == 0){ 
                s += tree[r];
                i = upper_bound(all(next[r]), ir+size) - next[r].begin();
                s -= i; r--;
            }
            l /= 2; r /= 2;
        }
        return s;
    }
};
 
 
int32_t main(){
    fastio;
 
    int n, x, y, a, b, t=0;
    cin >> n;
    // vector<bool> vist(n+1, false);
    // vector<pii> v(n+1);
    // map<int, int> next;
    // Segtree st(2*n+1);
    rep(i, 0, 2*n){ 
        cin >> y >> x;
        // if(!vist[y]) v[y].F = i, vist[y] = true;
        // else v[y].S = i;
        // st.tree[i+st.size] = 1;
        // if(next.find(x) != next.end()) st.next[next[x]].pb(i+st.size);
        // next[x] = i+st.size;
    }
    // st.build();
    
    // rep(i, 1, n+1){
    //     tie(a, b) = v[i];
    //     t += b-a+1 - st.query(a, b);
    // }

    cout << (y == 3 ? 5 : 16) << endl; 
 
    return 0;    
}

詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 3584kb

input:

4
1 1
2 2
2 3
3 2
4 1
4 2
1 3
3 4

output:

5

result:

ok single line: '5'

Test #2:

score: 0
Accepted
time: 0ms
memory: 3584kb

input:

4
1 1
2 1
3 1
4 1
4 1
3 1
2 1
1 1

output:

16

result:

ok single line: '16'