oj.uz

Submission #870166

# Submission time Handle Problem Language Result Execution time Memory
870166 2023-11-07T06:44:33 Z watse trapezoid (balkan11_trapezoid) C++14
100 / 100
 89 ms 18252 KB 
#include <bits/stdc++.h>
#define fi first
#define se second
#define tl fi.fi
#define tr fi.se
#define dl se.fi
#define dr se.se
#define pb push_back

using namespace std;

typedef long long ll;
typedef pair<int, int> ii;

const int NMAX = 5e5 + 5;
const ll inf = 1e9;
const int mod = 30013;
pair <ii,ii> a[NMAX];

ii bit[NMAX];
int n;
void update (int x, ii val){
    for (; x <= 2 * n; x += x & -x)
    if (bit[x].fi < val.fi)
        bit[x] = val;
    else 
    if (bit[x].fi == val.fi)
        bit[x].se = (bit[x].se + val.se) % mod;
}

ii get (int x){
    ii ans = {0,1};
    for (; x > 0; x -= x & -x)
    if (bit[x].fi > ans.fi)
        ans = bit[x];
    else if (bit[x].fi == ans.fi)
        ans.se = (ans.se + bit[x].se) % mod;
    return ans;
}

ii ret,res[NMAX];
vector <int> t,d;
int g[NMAX],u[NMAX];

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n;
    for (int i = 1; i <= n; ++i){
        cin >> a[i].tl >> a[i].tr >> a[i].dl >> a[i].dr;
        t.pb(a[i].tl);
        t.pb(a[i].tr);
        d.pb(a[i].dl);
        d.pb(a[i].dr);
    }
    sort(t.begin(),t.end());
    sort(d.begin(),d.end());
    t.erase(unique(t.begin(),t.end()),t.end());
    d.erase(unique(d.begin(),d.end()),d.end());
    for (int i = 1; i <= n; ++i){
        a[i].tl = lower_bound (t.begin(),t.end(),a[i].tl) - t.begin() + 1;
        a[i].tr = lower_bound (t.begin(),t.end(),a[i].tr) - t.begin() + 1;
        a[i].dl = lower_bound (d.begin(),d.end(),a[i].dl) - d.begin() + 1;
        a[i].dr = lower_bound (d.begin(),d.end(),a[i].dr) - d.begin() + 1;
        g[a[i].tl] = i;
        u[a[i].tr] = i;
    }
    for (int i = 1; i <= 2 * n; i++){
        if (g[i]){
            int v = g[i];
            ii f = get(a[v].dl);
            ++f.fi;
            res[v] = f;
            if (f.fi > ret.fi)
                ret = f;
            else if (f.fi == ret.fi)
                ret.se = (ret.se + f.se) % mod;
        }
        else {
            int v = u[i];
            update(a[v].dr,res[v]);
        }
    }
    cout << ret.fi << " " << ret.se;
    return 0;
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8536 KB Output is correct
2 Correct 1 ms 8680 KB Output is correct
3 Correct 1 ms 8540 KB Output is correct
4 Correct 2 ms 8536 KB Output is correct
5 Correct 2 ms 8540 KB Output is correct
6 Correct 3 ms 8728 KB Output is correct
7 Correct 4 ms 8796 KB Output is correct
8 Correct 5 ms 8796 KB Output is correct
9 Correct 9 ms 9052 KB Output is correct
10 Correct 17 ms 9688 KB Output is correct
11 Correct 21 ms 9940 KB Output is correct
12 Correct 44 ms 15300 KB Output is correct
13 Correct 52 ms 16072 KB Output is correct
14 Correct 61 ms 16572 KB Output is correct
15 Correct 68 ms 16928 KB Output is correct
16 Correct 73 ms 17020 KB Output is correct
17 Correct 83 ms 17340 KB Output is correct
18 Correct 74 ms 17596 KB Output is correct
19 Correct 78 ms 17852 KB Output is correct
20 Correct 89 ms 18252 KB Output is correct