oj.uz

Submission #1117209

# Submission time Handle Problem Language Result Execution time Memory
1117209 2024-11-23T01:19:01 Z vjudge1 trapezoid (balkan11_trapezoid) C++17
100 / 100
 242 ms 27208 KB 
#include<bits/stdc++.h>
using namespace std;
#define F first
#define S second
pair<int,int> operator+=(pair<int,int> &a,pair<int,int> b){
    if(a.F<b.F)
        return a=b;
    if(a.F>b.F)
        return a;
    a.S+=b.S;
    if(a.S>=30013)
        a.S-=30013;
    return a;
}
struct {
    pair<int,int> trrre[200100]; 
    pair<int,int>query(int x){
        pair<int,int>res;
        while(x)
            res+=trrre[x],x-=x&-x;
        return res;
    }
    void upd(int x,pair<int,int> c){
        c.first++;
        while(x<=2e5)
            trrre[x]+=c,x+=x&-x;
    }
} fenwick;
pair<int,int> vals[100100];
map<int,int>mp2;
map<int,array<int,3>>mp1;
int CC;
int main(){
    cin.tie(0)->sync_with_stdio(0);
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        int a,b,c,d;
        cin>>a>>b>>c>>d;
        mp2[a],mp2[b];
        mp1[c]={a,0,i};
        mp1[d]={b,1,i};
    }
    fenwick.upd(1,{0,1});
    for(auto&[i,j]:mp2)
        j=++CC;
    for(auto[i,j]:mp1){
        auto[pos,op,ind]=j;
        pos=mp2[pos];
        if(op) fenwick.upd(pos,vals[ind]);
        else vals[ind]=fenwick.query(pos);
    }
    pair<int,int>X = fenwick.query(mp2.size());
    cout<<X.F-1<<' '<<X.S<<'\n';
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 592 KB Output is correct
4 Correct 2 ms 592 KB Output is correct
5 Correct 3 ms 1000 KB Output is correct
6 Correct 4 ms 1160 KB Output is correct
7 Correct 5 ms 1528 KB Output is correct
8 Correct 7 ms 1616 KB Output is correct
9 Correct 15 ms 3320 KB Output is correct
10 Correct 26 ms 5712 KB Output is correct
11 Correct 36 ms 6992 KB Output is correct
12 Correct 100 ms 13880 KB Output is correct
13 Correct 100 ms 16716 KB Output is correct
14 Correct 148 ms 19220 KB Output is correct
15 Correct 146 ms 20652 KB Output is correct
16 Correct 176 ms 21832 KB Output is correct
17 Correct 163 ms 23208 KB Output is correct
18 Correct 127 ms 24648 KB Output is correct
19 Correct 177 ms 25936 KB Output is correct
20 Correct 242 ms 27208 KB Output is correct