Submission #1117423

#	Time	Username	Problem	Language	Result	Execution time	Memory
1117423		ntdaccode	trapezoid (balkan11_trapezoid)	C++17	30 / 100	235 ms	44064 KiB

trapezoid

#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 (stderr)

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 / 100