oj.uz

Submission #802062

# Submission time Handle Problem Language Result Execution time Memory
802062 2023-08-02T09:28:38 Z bachhoangxuan 허수아비 (JOI14_scarecrows) C++17
100 / 100
 1141 ms 29532 KB 
// Judges with GCC >= 12 only needs Ofast
// #pragma GCC optimize("O3,no-stack-protector,fast-math,unroll-loops,tree-vectorize")
// MLE optimization
// #pragma GCC optimize("conserve-stack")
// Old judges
// #pragma GCC target("sse4.2,popcnt,lzcnt,abm,mmx,fma,bmi,bmi2")
// New judges. Test with assert(__builtin_cpu_supports("avx2"));
// #pragma GCC target("avx2,popcnt,lzcnt,abm,bmi,bmi2,fma,tune=native")
// Atcoder
// #pragma GCC target("avx2,popcnt,lzcnt,abm,bmi,bmi2,fma")
/*
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
- insert(x),erase(x)
- find_by_order(k): return iterator to the k-th smallest element
- order_of_key(x): the number of elements that are strictly smaller
*/
#include<bits/stdc++.h>
using namespace std;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
uniform_real_distribution<> pp(0.0,1.0);
#define int long long
#define ld long double
#define pii pair<int,int>
#define piii pair<int,pii>
#define mpp make_pair
#define fi first
#define se second
const int inf=1e18;
const int mod=998244353;
const int maxn=200005;
const int bl=650;
const int maxs=655;
const int maxm=200005;
const int maxq=500005;
const int maxl=20;
const int maxa=250000;
const int root=3;
int power(int a,int n){
    int res=1;
    while(n){
        if(n&1) res=res*a%mod;
        a=a*a%mod;n>>=1;
    }
    return res;
}
const int iroot=power(3,mod-2);
const int base=101;
struct BIT{
    int n;
    vector<int> bit;
    BIT(int N):n(N){
        bit.assign(n+1,0);
    };
    void update(int x,int val){
        for(int i=x;i<=n;i+=(i&(-i))) bit[i]+=val;
    }
    int query(int x){
        int res=0;
        for(int i=x;i>=1;i-=(i&(-i))) res+=bit[i];
        return res;
    }
};
void solve(){
    int n;cin >> n;
    vector<int> x(n),y(n),cx,cy;
    for(int i=0;i<n;i++){
        cin >> x[i] >> y[i];
        cx.push_back(x[i]);
        cy.push_back(y[i]);
    }
    sort(cx.begin(),cx.end());
    sort(cy.begin(),cy.end());
    for(int i=0;i<n;i++){
        x[i]=lower_bound(cx.begin(),cx.end(),x[i])-cx.begin();
        y[i]=lower_bound(cy.begin(),cy.end(),y[i])-cy.begin();
    }
    int ans=0;
    vector<int> pos(n,0);
    for(int i=0;i<n;i++) pos[x[i]]=y[i]+1;

    BIT bit(n);

    function<void(int,int)> dnc = [&](int l,int r){
        if(r-l<=1) return;
        int mid=(l+r)>>1;
        dnc(l,mid);dnc(mid,r);
        //cout << l << ' ' << r << '\n';
        set<int> ss;
        vector<pii> q;
        for(int i=mid;i<r;i++){
            if(pos[i]){
                auto it=ss.upper_bound(pos[i]);
                int t=(it==ss.begin()?0LL:*(--it));
                q.push_back({pos[i],t});
                ss.insert(pos[i]);
            }
        }
        ss.clear();
        for(int i=mid-1;i>=l;i--){
            if(pos[i]){
                auto it=ss.lower_bound(pos[i]);
                int t=(it==ss.end()?n+1:*it);
                q.push_back({pos[i],-n-1});
                q.push_back({t,-pos[i]});
                ss.insert(pos[i]);
            }
        }
        sort(q.begin(),q.end());
        for(auto [a,b]:q){
            //cout << "* " << a << ' ' << b << '\n';
            if(b<-n) bit.update(a,1);
            else if(b<0) bit.update(-b,-1);
            else ans+=bit.query(a)-bit.query(b);
        }
    };
    dnc(0,n);
    cout << ans << '\n';
}

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);cout.tie(NULL);
    int test=1;//cin >> test;
    while(test--) solve();
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 328 KB Output is correct
5 Correct 1 ms 324 KB Output is correct
6 Correct 1 ms 328 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 340 KB Output is correct
9 Correct 2 ms 324 KB Output is correct
10 Correct 1 ms 340 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 924 KB Output is correct
2 Correct 14 ms 976 KB Output is correct
3 Correct 16 ms 972 KB Output is correct
4 Correct 10 ms 960 KB Output is correct
5 Correct 14 ms 900 KB Output is correct
6 Correct 18 ms 948 KB Output is correct
7 Correct 18 ms 960 KB Output is correct
8 Correct 14 ms 960 KB Output is correct
9 Correct 18 ms 968 KB Output is correct
10 Correct 16 ms 956 KB Output is correct
11 Correct 18 ms 960 KB Output is correct
12 Correct 11 ms 844 KB Output is correct

Subtask #3
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 699 ms 27792 KB Output is correct
2 Correct 1067 ms 29032 KB Output is correct
3 Correct 831 ms 28452 KB Output is correct
4 Correct 664 ms 29144 KB Output is correct
5 Correct 918 ms 29092 KB Output is correct
6 Correct 963 ms 29148 KB Output is correct
7 Correct 1104 ms 29108 KB Output is correct
8 Correct 1085 ms 29148 KB Output is correct
9 Correct 725 ms 29124 KB Output is correct
10 Correct 939 ms 29112 KB Output is correct
11 Correct 1000 ms 29112 KB Output is correct
12 Correct 1141 ms 29532 KB Output is correct
13 Correct 1099 ms 29160 KB Output is correct
14 Correct 682 ms 29132 KB Output is correct
15 Correct 994 ms 29256 KB Output is correct
16 Correct 1047 ms 29272 KB Output is correct
17 Correct 637 ms 16748 KB Output is correct
18 Correct 977 ms 29104 KB Output is correct
19 Correct 997 ms 28756 KB Output is correct
20 Correct 963 ms 28508 KB Output is correct