Submission #206163

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
206163	2020-03-02T14:13:30 Z	AlexLuchianov	trapezoid (balkan11_trapezoid)	C++14	100 / 100	451 ms	19560 KB

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

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.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	376 KB	Output is correct
2	Correct	5 ms	376 KB	Output is correct
3	Correct	6 ms	376 KB	Output is correct
4	Correct	7 ms	508 KB	Output is correct
5	Correct	11 ms	760 KB	Output is correct
6	Correct	15 ms	1016 KB	Output is correct
7	Correct	16 ms	888 KB	Output is correct
8	Correct	21 ms	1272 KB	Output is correct
9	Correct	42 ms	2596 KB	Output is correct
10	Correct	73 ms	3316 KB	Output is correct
11	Correct	103 ms	5868 KB	Output is correct
12	Correct	225 ms	11240 KB	Output is correct
13	Correct	268 ms	12776 KB	Output is correct
14	Correct	331 ms	15568 KB	Output is correct
15	Correct	353 ms	14256 KB	Output is correct
16	Correct	392 ms	15024 KB	Output is correct
17	Correct	403 ms	17764 KB	Output is correct
18	Correct	334 ms	12004 KB	Output is correct
19	Correct	417 ms	19172 KB	Output is correct
20	Correct	451 ms	19560 KB	Output is correct