oj.uz

답안 #878615

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
878615 2023-11-25T02:02:25 Z LTTrungCHL 사다리꼴 (balkan11_trapezoid) C++17
100 / 100
 160 ms 32064 KB 
///***LTT***///
/// ->NHAT QUOC GIA<- ///
#include<bits/stdc++.h>
//#pragma GCC optimize ("O3")
//#pragma GCC optimize ("unroll-loops")
//#pragma GCC target("popcnt")
#define int long long
#define endl "\n"
#define F first
#define S second
#define pb push_back
using namespace std;
const long long oo = 1e9+7;
const int N = 2 * 1e5 + 10;
const long long e = 30013;
priority_queue <pair <pair <int ,int> ,pair <int ,int>>> q;
int n, a[N], b[N], c[N], d[N];
vector <int> duyet;
pair <int ,int> tree[N * 4];
map <int ,int> nen;
vector <pair <pair <int ,int> ,pair <int ,int>>> v;
void mer(int id){
    if (tree[id * 2].F == tree[id * 2 + 1].F){
        tree[id] = {tree[id * 2].F, (tree[id * 2].S + tree[id * 2 +1].S)%e};
    } else {
        tree[id] = max(tree[id * 2], tree[id * 2 +1]);
    }
    return;
}
void update(int id,int l,int r,int u,int val,int val2){
    if (l > u or r < u) return;
    if (l == u and r == u){
        if (tree[id].F < val){
            tree[id].F = val;
            tree[id].S = val2;
        } else if (tree[id].F == val) {
            tree[id].S += val2;
            tree[id].S %=e;
        }
        return;
    }
    int mid = (l + r)/2;
    update(id * 2,l,mid,u,val,val2);
    update(id * 2 + 1,mid + 1,r,u,val,val2);
    mer(id);
    return;
}
pair <int ,int> get(int id,int l,int r,int u,int v){
    if (l > v or r < u) return {0,0};
    if (l >= u and r <= v) return tree[id];
    int mid = (l + r)/2;
    pair <int ,int> L = get(id *2,l,mid,u,v);
    pair <int ,int> R = get(id *2 + 1,mid + 1,r,u,v);
//    cout << L.F <<" "<< R.F <<" "<<L.S <<" "<<R.S <<"\n";
    if (L.F == R.F){
        return {L.F, (L.S + R.S)%e};
    } else {
        return max(L,R);
    }
}
void inp(){
    cin >> n;
    for (int i = 1;i <= n;i++){
        cin >> a[i] >> b[i] >> c[i] >> d[i];
        duyet.pb(c[i]);
        duyet.pb(d[i]);
    }
    return;
}
void solve(){
    sort(duyet.begin(), duyet.end());
    nen[duyet[0]] = 1;
    int tt = 1;
    for (int i = 1;i < duyet.size();i++){
        if (duyet[i] > duyet[i-1]){
            ++tt;
            nen[duyet[i]] = tt;
        }
    }
    for (int i = 1;i <= n;i++){
        c[i] = nen[c[i]];
        d[i] = nen[d[i]];
        v.pb({{a[i], b[i]}, {c[i], d[i]}});
    }
    sort(v.begin(), v.end());
    update(1,0,tt,0,0,1);
//    cout << get(1,0,tt,0,tt).S <<"\n";
    for (auto x : v){
        while (!q.empty() and -q.top().F.F < x.F.F){
            update(1,0,tt,q.top().S.F,q.top().S.S,q.top().F.S);
            q.pop();
        }
        pair <int ,int> res = get(1,0,tt,0,x.S.F - 1);
        q.push({ {-x.F.S, res.S%e}, {x.S.S,res.F + 1}});
    }
    while (!q.empty()){
        update(1,0,tt,q.top().S.F,q.top().S.S,q.top().F.S);
        q.pop();
    }
    pair <int ,int> ans = get(1,0,tt,1,tt);
    cout << ans.F <<" "<< ans.S <<"\n";
    return;
}
signed main(){
    ios_base::sync_with_stdio(NULL);
    cin.tie(NULL);
    cout.tie(NULL);
    if (fopen("ltt.inp", "r")){
        freopen("ltt.inp", "r", stdin);
        freopen("ltt.out", "w", stdout);
    }
    //int t;
    //cin >> t;
    //while(t--){
    inp();
    solve();
    //}
}

Compilation message

trapezoid.cpp: In function 'void solve()':
trapezoid.cpp:74:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   74 |     for (int i = 1;i < duyet.size();i++){
      |                    ~~^~~~~~~~~~~~~~
trapezoid.cpp: In function 'int main()':
trapezoid.cpp:109:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  109 |         freopen("ltt.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
trapezoid.cpp:110:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  110 |         freopen("ltt.out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
100.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 1 ms 6748 KB Output is correct
4 Correct 2 ms 6748 KB Output is correct
5 Correct 3 ms 7116 KB Output is correct
6 Correct 4 ms 7516 KB Output is correct
7 Correct 6 ms 7516 KB Output is correct
8 Correct 7 ms 7896 KB Output is correct
9 Correct 14 ms 9412 KB Output is correct
10 Correct 27 ms 12116 KB Output is correct
11 Correct 36 ms 12748 KB Output is correct
12 Correct 81 ms 19468 KB Output is correct
13 Correct 96 ms 21068 KB Output is correct
14 Correct 108 ms 26680 KB Output is correct
15 Correct 122 ms 28836 KB Output is correct
16 Correct 139 ms 30592 KB Output is correct
17 Correct 140 ms 30144 KB Output is correct
18 Correct 130 ms 30268 KB Output is correct
19 Correct 151 ms 31116 KB Output is correct
20 Correct 160 ms 32064 KB Output is correct