Submission #206163

#	Time	Username	Problem	Language	Result	Execution time	Memory
206163		AlexLuchianov	trapezoid (balkan11_trapezoid)	C++14	100 / 100	451 ms	19560 KiB

trapezoid

#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <algorithm>
#include <map>

using namespace std;

ifstream in ("trapezoid.in");
ofstream out ("trapezoid.out");

#define MIN(a, b) (((a) < (b)) ? (a) : (b))
#define MAX(a, b) (((a) < (b)) ? (b) : (a))
using ll = long long;
using ld = long double;

int const nmax = 100000;
int const modulo = 30013;

struct Trapezoid{
  int a;
  int b;
  int c;
  int d;
} v[1 + nmax];

int normalize(int n){
  vector<int> temp;
  for(int i = 1;i <= n; i++) {
    temp.push_back(v[i].a);
    temp.push_back(v[i].b);
    temp.push_back(v[i].c);
    temp.push_back(v[i].d);
  }
  sort(temp.begin(), temp.end());
  temp.erase(unique(temp.begin(), temp.end()), temp.end());
  map<int,int> code;
  for(int i = 0; i < temp.size(); i++)
    code[temp[i]] = 1 + i;
  for(int i = 1;i <= n; i++){
    v[i].a = code[v[i].a];
    v[i].b = code[v[i].b];
    v[i].c = code[v[i].c];
    v[i].d = code[v[i].d];
  }
  return temp.size();
}

pair<int,int> combine(pair<int,int> a, pair<int,int> b){
  if(a.first == b.first)
    return {a.first, (b.second + a.second) % modulo};
  else
    return max(a, b);
}

class FenwickTree{
private:
  int n;
  vector<pair<int,int>> aib;
public:
  FenwickTree(int n_){
    n = n_;
    aib.resize(1 + n);
  }

  void update(int pos, pair<int,int> number){
    for(int x = pos; x <= n; x += (x ^ (x & (x - 1))))
      aib[x] = combine(aib[x], number);
  }

  pair<int,int> query(int pos){
    pair<int,int> result(0,0);
    for(int x = pos; 0 < x; x = x & (x - 1))
      result = combine(result, aib[x]);
    return result;
  }
};

vector<pair<int,int>> events;
bool compare(pair<int,int> x, pair<int,int> y){
  int valx, valy;
  if(x.second == 1)
    valx = v[x.first].a;
  else
    valx = v[x.first].b;

  if(y.second == 1)
    valy = v[y.first].a;
  else
    valy = v[y.first].b;
  return valx < valy;
}

pair<int,int> dp[1 + nmax];
int main()
{
  int n;
  cin >> n;
  for(int i = 1;i <= n; i++)
    cin >> v[i].a >> v[i].b >> v[i].c >> v[i].d;
  int lim = normalize(n);
  for(int i = 1;i <= n; i++) {
    events.push_back({i, 1});
    events.push_back({i, 2});
  }

  sort(events.begin(), events.end(), compare);
  FenwickTree aib(lim);

  for(int i = 0; i < events.size(); i++){
    int id = events[i].first;
    if(events[i].second == 1){
      dp[id] = aib.query(v[id].c);
      dp[id].first++;
      if(dp[id].first == 1)
        dp[id].second = 1;
    } else
      aib.update(v[id].d, dp[id]);
  }
  pair<int,int> result(0, 0);

  for(int i = 1;i <= n; i++)
    result = combine(result, dp[i]);
  cout << result.first << " " << result.second << '\n';
  return 0;
}

Compilation message (stderr)

trapezoid.cpp: In function 'int normalize(int)':
trapezoid.cpp:39:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0; i < temp.size(); i++)
                  ~~^~~~~~~~~~~~~
trapezoid.cpp: In function 'int main()':
trapezoid.cpp:111:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0; i < events.size(); i++){
                  ~~^~~~~~~~~~~~~~~

• Subtask 1: 100 / 100