oj.uz

Submission #1101263

# Submission time Handle Problem Language Result Execution time Memory
1101263 2024-10-16T01:27:43 Z KawakiMeido trapezoid (balkan11_trapezoid) C++17
46 / 100
 125 ms 15028 KB 
/*Author: KawakiMeido*/
#include <bits/stdc++.h>
#define pb push_back
#define endl "\n"
#define ll long long
#define all(x) (x).begin(),(x).end()
#define pii pair<int,int>
#define piiii pair<pii,pii>
#define fi first
#define se second

using namespace std;

/*Constants*/
const int N = 2e5+10;
const int INF = 1e9+7;
const long long LLINF = 1e18+3;

/*TestCases*/
int test=1;
void solve();
void TestCases(bool v){
    if (v) cin >> test;
    while(test--) solve();
}

/*Global Variables*/
int n;
vector<int> cmpx,cmpy;
vector<piiii> query;

//SEGG
pii ST[N*4];
pii ans[N];

pii Comb(pii x, pii y){
    if (x.fi!=y.fi){
        return max(x,y);
    }
    else return make_pair(x.fi,x.se+y.se);
}

void Update(int idx, int l, int r, int x, pii val){
    if (x<l || r<x) return;
    if (l==r){
        ST[idx] = Comb(val,ST[idx]);
        return;
    }
    int mid = (l+r)/2;
    Update(idx*2,l,mid,x,val); Update(idx*2+1,mid+1,r,x,val);
    ST[idx] = Comb(ST[idx*2],ST[idx*2+1]);
}

pii Get(int idx, int l, int r, int x, int y){
    if (y<l || r<x) return make_pair(0,0);
    if (x<=l && r<=y) return ST[idx];
    int mid = (l+r)/2;
    return Comb(Get(idx*2,l,mid,x,y),Get(idx*2+1,mid+1,r,x,y));
}

/*Solution*/
void solve(){
    cin >> n;
    for (int i=1; i<=n; i++){
        int x1,x2,y1,y2; cin >> x1 >> x2 >> y1 >> y2;
        cmpx.push_back(x1);
        cmpx.push_back(x2);
        cmpy.push_back(y1);
        cmpy.push_back(y2);
        query.push_back({{y1,1},{x1,i}});
        query.push_back({{y2,0},{x2,i}});
    }
    sort(all(cmpx));
    sort(all(cmpy));
    for (int i=0; i<(int)query.size(); i++){
        query[i].fi.fi = lower_bound(all(cmpy),query[i].fi.fi)-cmpy.begin()+1;
        query[i].se.fi = lower_bound(all(cmpx),query[i].se.fi)-cmpx.begin()+1;
    }
    sort(all(query));
    int idx = 0;
    for (int i=1; i<=(int)cmpy.size(); i++){
        while (idx!=(int)query.size() && query[idx].fi.fi == i){
//            int y = i;
            int x = query[idx].se.fi;
            int ver = query[idx].fi.se;
            int id = query[idx].se.se;

            if (ver){
                pii res = Get(1,1,(int)cmpx.size(),1,x-1);
                if (res == make_pair(0,0)) res.se++;
                res.fi++;
                ans[id] = res;
            }
            else{
                Update(1,1,(int)cmpx.size(),x,ans[id]);
            }
            ++idx;
        }
    }
    pii res = make_pair(0,0);
    for (int i=1; i<=n; i++){
        res = Comb(res,ans[i]);
    }
    cout << res.fi << " " << res.se << endl;
}

/*Driver Code*/
signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    TestCases(0);

    return 0;
}

Subtask #1
46.0 / 100.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 Partially correct 1 ms 340 KB Partially correct
4 Partially correct 2 ms 484 KB Partially correct
5 Partially correct 3 ms 596 KB Partially correct
6 Partially correct 4 ms 852 KB Partially correct
7 Partially correct 5 ms 992 KB Partially correct
8 Partially correct 6 ms 1232 KB Partially correct
9 Partially correct 12 ms 1904 KB Partially correct
10 Partially correct 23 ms 3272 KB Partially correct
11 Partially correct 31 ms 3776 KB Partially correct
12 Partially correct 62 ms 7624 KB Partially correct
13 Partially correct 74 ms 7868 KB Partially correct
14 Partially correct 97 ms 13492 KB Partially correct
15 Partially correct 106 ms 13756 KB Partially correct
16 Partially correct 109 ms 14004 KB Partially correct
17 Partially correct 110 ms 14260 KB Partially correct
18 Partially correct 102 ms 14428 KB Partially correct
19 Partially correct 114 ms 14264 KB Partially correct
20 Partially correct 125 ms 15028 KB Partially correct