mickypinata

TOI10: Treasure Chest

Jun 11th, 2021
718
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. enum cmd {
  5.     ADD = 0, DEL = 1
  6. };
  7.  
  8. struct event {
  9.     int idx, mul;
  10.     cmd add;
  11.     event(){}
  12.     event(int i, int m, cmd a){
  13.         idx = i;
  14.         mul = m;
  15.         add = a;
  16.     }
  17.     bool operator < (const event &rhs) const {
  18.         if(idx != rhs.idx){
  19.             return idx < rhs.idx;
  20.         } else if(add != rhs.add){
  21.             return add > rhs.add;
  22.         } else {
  23.             return mul < rhs.mul;
  24.         }
  25.     }
  26. };
  27.  
  28. typedef long long lli;
  29. typedef pair<int, int> pii;
  30.  
  31. int curr[4];
  32. vector<int> prime = {2, 3, 5, 7};
  33. vector<pii> factor[11];
  34. vector<event> ev;
  35.  
  36. int primeIdx(int x){
  37.     return lower_bound(prime.begin(), prime.end(), x) - prime.begin();
  38. }
  39.  
  40. int main(){
  41.  
  42.     factor[2] = {pii(2, 1)};
  43.     factor[3] = {pii(3, 1)};
  44.     factor[4] = {pii(2, 2)};
  45.     factor[5] = {pii(5, 1)};
  46.     factor[6] = {pii(2, 1), pii(3, 1)};
  47.     factor[7] = {pii(7, 1)};
  48.     factor[8] = {pii(2, 3)};
  49.     factor[9] = {pii(3, 2)};
  50.     factor[10] = {pii(2, 1), pii(5, 1)};
  51.  
  52.     int nArr, Q;
  53.     scanf("%d%d", &Q, &nArr);
  54.     for(int q = 1; q <= Q; ++q){
  55.         int mul, st, ed;
  56.         scanf("%d%d%d", &mul, &st, &ed);
  57.         ev.emplace_back(st, mul, ADD);
  58.         ev.emplace_back(ed + 1, mul, DEL);
  59.     }
  60.     ev.emplace_back(nArr, 1, ADD);
  61.     sort(ev.begin(), ev.end());
  62.  
  63.     lli mx = 0;
  64.     int mxCnt = 0;
  65.     int currIdx = 0;
  66.     for(event e : ev){
  67.         int idx = e.idx;
  68.         int mul = e.mul;
  69.         cmd add = e.add;
  70.         if(idx != currIdx){
  71.             lli nFactor = 1;
  72.             for(int cnt : curr){
  73.                 nFactor *= (cnt + 1);
  74.             }
  75.             if(nFactor > mx){
  76.                 mx = nFactor;
  77.                 mxCnt = idx - currIdx;
  78.             } else if(nFactor == mx){
  79.                 mxCnt += idx - currIdx;
  80.             }
  81.             currIdx = idx;
  82.         }
  83.         if(add == ADD){
  84.             for(pii f : factor[mul]){
  85.                 int x = f.first;
  86.                 int cnt = f.second;
  87.                 curr[primeIdx(x)] += cnt;
  88.             }
  89.         } else if(add == DEL){
  90.             for(pii f : factor[mul]){
  91.                 int x = f.first;
  92.                 int cnt = f.second;
  93.                 curr[primeIdx(x)] -= cnt;
  94.             }
  95.         }
  96.     }
  97.     cout << mx << ' ' << mxCnt;
  98.  
  99.     return 0;
  100. }
  101.  
RAW Paste Data