oj.uz

답안 #467523

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
467523 2021-08-23T12:24:26 Z Vladth11 사다리꼴 (balkan11_trapezoid) C++14
100 / 100
 392 ms 21268 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 AINT{
public:
    pii aint[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(int node, int st, int dr, int a, pii b){
        if(st == dr){
            aint[node] = b;
            return;
        }
        int mid = (st + dr) / 2;
        if(a <= mid){
            update(node * 2, st, mid, a, b);
        }else{
            update(node * 2 + 1, mid + 1, dr, a, b);
        }
        aint[node] = combine(aint[node * 2], aint[node * 2 + 1]);
    }
    pii query(int node, int st, int dr, int a, int b){
        if(a <= st && dr <= b){
            return aint[node];
        }
        int 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(int a, pii b){
        update(1, 1, NMAX - 1, a, b);
    }
    pii prefix(int x){
        return query(1, 1, NMAX - 1, 1, x); ///sa evit 0
    }
}st;

struct ura{
    int a, b, c, d;
};

bool cmp(ura a, ura b){
    return a.a < b.a;
}

pii dp[100001];
ura v[100001];

vector <int> nrm;
map <int, int> mp;

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

Subtask #1
100.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 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 564 KB Output is correct
5 Correct 6 ms 716 KB Output is correct
6 Correct 9 ms 972 KB Output is correct
7 Correct 12 ms 1228 KB Output is correct
8 Correct 16 ms 1372 KB Output is correct
9 Correct 35 ms 2440 KB Output is correct
10 Correct 65 ms 4600 KB Output is correct
11 Correct 87 ms 5424 KB Output is correct
12 Correct 186 ms 11108 KB Output is correct
13 Correct 224 ms 13232 KB Output is correct
14 Correct 272 ms 15220 KB Output is correct
15 Correct 298 ms 16400 KB Output is correct
16 Correct 328 ms 17652 KB Output is correct
17 Correct 344 ms 18616 KB Output is correct
18 Correct 340 ms 19340 KB Output is correct
19 Correct 360 ms 19232 KB Output is correct
20 Correct 392 ms 21268 KB Output is correct