oj.uz

답안 #1092223

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1092223 2024-09-23T15:39:45 Z NguyenPhucThang 사다리꼴 (balkan11_trapezoid) C++17
40 / 100
 101 ms 17656 KB 
#include <bits/stdc++.h>
#define forr(i, a, b) for (int i = (a); i <= (b); i++)
#define ford(i, a, b) for (int i = (a); i >= (b); i--)
#define forf(i, a, b) for (int i = (a); i < (b); i++)
#define fi first
#define se second
#define pb push_back
#define all(v) v.begin(), v.end()
#define ll long long
#define ld long double
#define pii pair<int, int>
#define pll pair<ll, ll>
#define vi vector<int>
#define vii vector<pii>
#define mask(i) (1LL << (i))
#define bit(x, i) (((x) >> (i)) & 1)
#define bp __builtin_popcountll
#define file "trapezoid"

using namespace std;
const int base = 31;
const ll mod = 1e9 + 7;
const ll oo = 1e18;
const int N = 1e6 + 5;

struct event{
   int x, y, type, idx;

   bool operator < (const event &other){
      if (x == other.x) return y < other.y;
      return x < other.x;
   }
};


pll st[4 * N];

pll combine(pll a, pll b){
   if (!a.fi && !b.fi) return {a.fi, 1};
   if (a.fi == b.fi) return {a.fi, a.se + b.se};
   return (a.fi < b.fi ? b : a);
}

void build(int id, int l, int r){
   st[id] = {0, 1};
   if (l == r) return;
   int mid = (l + r) >> 1;
   build(2 * id, l, mid), build(2 * id + 1, mid + 1, r);
   st[id] = combine(st[2 * id], st[2 * id + 1]);
}


void update(int id, int l, int r, int i, pll v){
   if (i < l || r < i) return;
   if (l == r){
      st[id] = combine(st[id], v);
      return;
   }

   int mid = (l + r) >> 1;
   update(2 * id, l, mid, i, v), update(2 * id + 1, mid + 1, r, i, v);
   st[id] = combine(st[2 * id], st[2 * id + 1]);
}

pll get(int id, int l, int r, int u, int v){
   if (v < l || r < u) return {0, 1};
   if (u <= l && r <= v) return st[id];
   int mid = (l + r) >> 1;
   return combine(get(2 * id, l, mid, u, v), get(2 * id + 1, mid + 1, r, u, v));
}

ll dp[N], cnt[N];

int main()
{
   ios_base::sync_with_stdio(0);
   cin.tie(0);

   int n;
   cin >> n;
   vector<event> v;
   vector<int> nen;
   forr(i, 1, n) {
      int a, b, c, d;
      cin >> a >> b >> c >> d;
      if (a > b) swap(a, b);
      if (c > d) swap(c, d);  
      v.pb({a, c, 0, i});
      v.pb({b, d, 1, i});  
      nen.pb(c);
      nen.pb(d);
   }

   sort(all(nen));
   nen.resize(unique(all(nen)) - nen.begin());
   forf(i, 0, v.size()) {
      v[i].y = lower_bound(all(nen), v[i].y) - nen.begin() + 1;
   }

   forr(i, 1, n) cnt[i] = 1;
   build(1, 1, 2e5);

   sort(all(v));

   forf(i, 0, v.size()){
      if (v[i].type == 0){
         pll ans = get(1, 1, 2e5, 1, v[i].y - 1);
         int id = v[i].idx;
         dp[id] = ans.fi + 1;
         cnt[id] = ans.se;
      }
      else {
         int id = v[i].idx;
         update(1, 1, 2e5, v[i].y, {dp[id], cnt[id]});
      }
   }  

   int res_dp = 0, res_cnt;
   forr(i, 1, n) if (res_dp < dp[i]) res_dp = dp[i], res_cnt = cnt[i];
   cout << res_dp << " " << res_cnt;

   return 0;
}

Compilation message

trapezoid.cpp: In function 'int main()':
trapezoid.cpp:4:43: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<event>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    4 | #define forf(i, a, b) for (int i = (a); i < (b); i++)
      |                                           ^
trapezoid.cpp:96:4: note: in expansion of macro 'forf'
   96 |    forf(i, 0, v.size()) {
      |    ^~~~
trapezoid.cpp:4:43: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<event>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    4 | #define forf(i, a, b) for (int i = (a); i < (b); i++)
      |                                           ^
trapezoid.cpp:105:4: note: in expansion of macro 'forf'
  105 |    forf(i, 0, v.size()){
      |    ^~~~
trapezoid.cpp:120:29: warning: 'res_cnt' may be used uninitialized in this function [-Wmaybe-uninitialized]
  120 |    cout << res_dp << " " << res_cnt;
      |                             ^~~~~~~

Subtask #1
40.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Partially correct 5 ms 8540 KB Partially correct
2 Partially correct 4 ms 8540 KB Partially correct
3 Partially correct 4 ms 8500 KB Partially correct
4 Partially correct 5 ms 8540 KB Partially correct
5 Partially correct 5 ms 8796 KB Partially correct
6 Partially correct 7 ms 8796 KB Partially correct
7 Partially correct 7 ms 9052 KB Partially correct
8 Partially correct 9 ms 9240 KB Partially correct
9 Partially correct 14 ms 9524 KB Partially correct
10 Partially correct 22 ms 10516 KB Partially correct
11 Partially correct 27 ms 10768 KB Partially correct
12 Partially correct 58 ms 13060 KB Partially correct
13 Partially correct 65 ms 13828 KB Partially correct
14 Partially correct 74 ms 15440 KB Partially correct
15 Partially correct 79 ms 15588 KB Partially correct
16 Partially correct 96 ms 16120 KB Partially correct
17 Partially correct 91 ms 16680 KB Partially correct
18 Partially correct 88 ms 17144 KB Partially correct
19 Partially correct 98 ms 17404 KB Partially correct
20 Partially correct 101 ms 17656 KB Partially correct