oj.uz

답안 #1117423

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1117423 2024-11-23T14:43:16 Z ntdaccode 사다리꼴 (balkan11_trapezoid) C++17
30 / 100
 235 ms 44064 KB 
#include<bits/stdc++.h>
#define fori(i,a,b) for(int i=a;i<=b;i++)
#define pb push_back

using namespace std;
typedef pair<int,int> ii;
typedef tuple<int,int,int> tp;
const int M=1e5+10;
const int N=4e5+10;
const int mod = 30013;

int n,m,a[M],b[M],c[M],d[M];

vector<int> rrh;

struct node
{
   int l,r,idx;
};
vector<node> L[N],R[N];

struct segment_tree
{
   ii t[4 * N];
   ii merged(const ii & l,const ii & r)
   {
      ii ret ={0,0} ;
      ret.first = max(l.first,r.first);
      if(l.first == ret.first) ret.second = l.second;
      if(r.first == ret.first) ret.second += r.second;
      ret.second %= mod;
      return ret;
   }
   void upd(int s, int l, int r, int pos, int val, int cnt)
   {
      if(l > pos || pos > r) return ;
      if(l == r) {
         if(t[s].first == val) t[s].second += cnt;
         else t[s] = {val,cnt};
         t[s].second %= mod;
         return ;
      }
      int mid = (l + r)/2;
      upd(s *2, l, mid, pos, val, cnt);
      upd(s * 2 + 1, mid + 1, r, pos, val, cnt);
      t[s] = merged(t[s * 2],t[s * 2 + 1]);
   }
   ii get(int s, int l, int r, int u, int v)
   {
      if(l > v || r < u) return {0,0};
      if(u <= l && r <= v) return t[s];
      int mid = (l + r)/2;
      return merged(get(s * 2, l, mid, u, v),get(s * 2 + 1, mid + 1, r, u, v));
   }

} T[2];

ii merged(const ii & l,const ii & r)
{
   ii ret ={0,0} ;
   ret.first = max(l.first,r.first);
   if(l.first == ret.first) ret.second = l.second;
   if(r.first == ret.first) ret.second += r.second;
   return ret;
}

int f[M],g[M];

int32_t main()
{
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  if(fopen("1.inp","r"))
  {
    freopen("1.inp","r",stdin);
    freopen("1.out","w",stdout);
  }
  #define task ""
  if(fopen(task".inp","r"))
  {
    freopen(task".inp","r",stdin);
    freopen(task".out","w",stdout);
  }

  cin >> n;
  for(int i = 1;i <= n; i++) {
      cin >> a[i] >> b[i] >> c[i] >> d[i];
      rrh.pb(a[i]),rrh.pb(b[i]),rrh.pb(c[i]),rrh.pb(d[i]);
  }

  sort(rrh.begin(),rrh.end());
  rrh.resize(unique(rrh.begin(),rrh.end()) - rrh.begin());
   m = rrh.size();
  for(int i = 1;i <= n ; i++) {
      a[i] = lower_bound(rrh.begin(),rrh.end(),a[i]) - rrh.begin() + 1;
      b[i] = lower_bound(rrh.begin(),rrh.end(),b[i]) - rrh.begin() + 1;
      c[i] = lower_bound(rrh.begin(),rrh.end(),c[i]) - rrh.begin() + 1;
      d[i] = lower_bound(rrh.begin(),rrh.end(),d[i]) - rrh.begin() + 1;
      //cerr << a[i] << " " << b[i] << " " << c[i] << " " << d[i] << "\n";
      L[a[i]].pb({c[i],d[i],i});
      R[b[i]].pb({c[i],d[i],i});
  }

  for(int i = 1;i <= m; i++) {
      for(node pos : L[i]) {
         ii x = merged(T[0].get(1, 1, m, 1, pos.l - 1),T[1].get(1, 1, m, pos.r + 1, m));
         if(x.first == 0) x.second = 1;
         x.first++;
         x.second %= mod;
         f[pos.idx] = x.first;
         g[pos.idx] = x.second;
//         cout << i  << " " << pos.l << " " << pos.r << " ";
//         cout << pos.idx << " " << f[pos.idx] << " " << g[pos.idx] << "\n";
      }
      for(node pos : R[i]) {
         T[0].upd(1, 1, m, pos.r, f[pos.idx], g[pos.idx]);
         T[1].upd(1, 1, m, pos.l, f[pos.idx], g[pos.idx]);
//         cout << i << " " << pos.l << " " << pos.r << " ";
//         cout << pos.idx << " " << f[pos.idx] << " " << g[pos.idx] << "\n";
      }
  }


  cout << T[1].t[1].first << " " << T[1].t[1].second % mod << " ";

}

Compilation message

trapezoid.cpp: In function 'int32_t main()':
trapezoid.cpp:76:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   76 |     freopen("1.inp","r",stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~
trapezoid.cpp:77:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   77 |     freopen("1.out","w",stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~
trapezoid.cpp:82:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   82 |     freopen(task".inp","r",stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
trapezoid.cpp:83:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   83 |     freopen(task".out","w",stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
30.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 14 ms 19280 KB Output is correct
2 Correct 13 ms 19280 KB Output is correct
3 Incorrect 14 ms 19280 KB Output isn't correct
4 Correct 15 ms 19280 KB Output is correct
5 Incorrect 16 ms 19536 KB Output isn't correct
6 Incorrect 21 ms 20048 KB Output isn't correct
7 Correct 19 ms 19836 KB Output is correct
8 Incorrect 24 ms 20060 KB Output isn't correct
9 Incorrect 32 ms 21532 KB Output isn't correct
10 Correct 50 ms 23116 KB Output is correct
11 Incorrect 61 ms 25288 KB Output isn't correct
12 Incorrect 109 ms 30148 KB Output isn't correct
13 Incorrect 140 ms 34260 KB Output isn't correct
14 Incorrect 174 ms 40640 KB Output isn't correct
15 Incorrect 173 ms 34888 KB Output isn't correct
16 Incorrect 204 ms 36544 KB Output isn't correct
17 Incorrect 209 ms 44064 KB Output isn't correct
18 Correct 181 ms 37828 KB Output is correct
19 Incorrect 209 ms 41408 KB Output isn't correct
20 Incorrect 235 ms 43456 KB Output isn't correct