oj.uz

답안 #467522

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
467522 2021-08-23T12:23:54 Z Vladth11 사다리꼴 (balkan11_trapezoid) C++14
100 / 100
 451 ms 26732 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define debug(x) cerr << #x << " " << x << "\n"
#define debugs(x) cerr << #x << " " << x << " "
#pragma GCC optimize("Ofast,unroll-loops")
 
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef pair <ll, ll> pii;
typedef pair <long double, pii> muchie;
typedef tree <ll, null_type, less_equal <ll>, rb_tree_tag, tree_order_statistics_node_update> OST;
 
const ll NMAX = 400001;
const ll INF = (1LL << 60);
const ll HALF = (1LL << 59);
const ll MOD = 30013;
const ll BLOCK = 318;
const ll base = 31;
const ll nr_of_bits = 21;
 
class All{
public:
    pii all[4 * NMAX];
    pii combine(pii a, pii b){
        if(a.first > b.first)
            return a;
        if(a.first < b.first)
            return b;
        return {a.first, (a.second + b.second) % MOD};
    }
    void update(ll node, ll st, ll dr, ll a, pii b){
        if(st == dr){
          	b.second %= MOD;
            all[node] = b;
            return;
        }
        ll mid = (st + dr) / 2;
        if(a <= mid){
            update(node * 2, st, mid, a, b);
        }else{
            update(node * 2 + 1, mid + 1, dr, a, b);
        }
        all[node] = combine(all[node * 2], all[node * 2 + 1]);
    }
    pii query(ll node, ll st, ll dr, ll a, ll b){
        if(a <= st && dr <= b){
            return all[node];
        }
        ll mid = (st + dr) / 2;
        pii rez = {-1, 0};
        if(a <= mid){
            rez = combine(rez, query(node * 2, st, mid, a, b));
        }
        if(b > mid){
            rez = combine(rez, query(node * 2 + 1, mid + 1, dr, a, b));
        }
        return rez;
    }
    void set(ll a, pii b){
        update(1, 1, NMAX - 1, a, b);
    }
    pii prefix(ll x){
        return query(1, 1, NMAX - 1, 1, x); ///sa evit 0
    }
}st;
 
struct ura{
    ll a, b, c, d;
};
 
bool cmp(ura a, ura b){
    return a.a < b.a;
}
 
pii dp[400001];
ura v[400001];
 
vector <ll> nrm;
map <ll, ll> mp;
 
int main() {
    ll n, i;
    cin >> n;
    for(i = 1; i <= n; i++){
        cin >> v[i].a >> v[i].b >> v[i].c >> v[i].d;
        nrm.push_back(v[i].a);
        nrm.push_back(v[i].b);
    }
    ///normalizare
    ll cnt = 0;
    sort(nrm.begin(), nrm.end());
    for(i = 0; i < nrm.size(); i++){
        if(i == 0 || nrm[i] != nrm[i - 1])
            cnt++;
        mp[nrm[i]] = cnt;
    }
    nrm.clear();
    for(i = 1; i <= n; i++){
        v[i].a = mp[v[i].a];
        v[i].b = mp[v[i].b];
          nrm.push_back(v[i].c);
        nrm.push_back(v[i].d);
    }
    mp.clear();
    sort(nrm.begin(), nrm.end());
    for(i = 0; i < nrm.size(); i++){
        if(i == 0 || nrm[i] != nrm[i - 1])
            cnt++;
        mp[nrm[i]] = cnt;
    }
    nrm.clear();
     for(i = 1; i <= n; i++){
        v[i].c = mp[v[i].c];
        v[i].d = mp[v[i].d];
    }
    mp.clear();
    ///gata
    sort(v + 1, v + n + 1, cmp);
    priority_queue <pii> pq; ///daca sortez dupa b, scot logul
    pii sol = {0, 0};
    st.set(1, {0, 1});
    for(i = 1; i <= n; i++){
        while(pq.size() && (-pq.top().first) <= v[i].a){
            st.set(v[pq.top().second].d, dp[pq.top().second]);
            pq.pop();
        }
        dp[i] = st.prefix(v[i].c);
        dp[i].first++;
        pq.push({-v[i].b, i});
        sol = st.combine(sol, dp[i]);
    }
    cout << sol.first << " " << sol.second << "\n";
    return 0;
}

Compilation message

trapezoid.cpp: In function 'int main()':
trapezoid.cpp:94:18: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   94 |     for(i = 0; i < nrm.size(); i++){
      |                ~~^~~~~~~~~~~~
trapezoid.cpp:108:18: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  108 |     for(i = 0; i < nrm.size(); i++){
      |                ~~^~~~~~~~~~~~

Subtask #1
100.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 2 ms 460 KB Output is correct
4 Correct 3 ms 588 KB Output is correct
5 Correct 7 ms 928 KB Output is correct
6 Correct 9 ms 1100 KB Output is correct
7 Correct 14 ms 1484 KB Output is correct
8 Correct 17 ms 1740 KB Output is correct
9 Correct 34 ms 2992 KB Output is correct
10 Correct 73 ms 5692 KB Output is correct
11 Correct 93 ms 6856 KB Output is correct
12 Correct 202 ms 13780 KB Output is correct
13 Correct 248 ms 16640 KB Output is correct
14 Correct 296 ms 19132 KB Output is correct
15 Correct 352 ms 20508 KB Output is correct
16 Correct 356 ms 21932 KB Output is correct
17 Correct 409 ms 23188 KB Output is correct
18 Correct 369 ms 24372 KB Output is correct
19 Correct 451 ms 24504 KB Output is correct
20 Correct 450 ms 26732 KB Output is correct