fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. typedef long long ll;
  4. typedef long double ld;
  5. typedef pair<int, int> pii;
  6. typedef pair<ll, ll> pll;
  7. typedef vector<int> vi;
  8. typedef vector<ll> vll;
  9. #define pb push_back
  10. #define ff first
  11. #define ss second
  12.  
  13. struct ruter{
  14.     int p, c, a, b, ind;
  15. };
  16.  
  17. struct stan{
  18.     int i, j, dl;
  19. };
  20.  
  21. bool cmp1(const ruter& a, const ruter& b){
  22.     return a.p < b.p;
  23. }
  24.  
  25. bool cmp2(const stan& a, const stan& b){
  26.     return a.dl > b.dl;
  27. }
  28.  
  29. const int NMAX = 2e3 + 1;
  30. const int INF = 2e9 + 7;
  31.  
  32. int minuj[NMAX][NMAX], maxuj[NMAX][NMAX], dp[NMAX][NMAX];
  33.  
  34. void build(vi& h){
  35.     int n = h.size() - 1;
  36.  
  37.     for(int i = 1; i <= n; i++){
  38.         for(int j = i + 1; j <= n; j++){
  39.             minuj[i][j] = min(minuj[i][j - 1], h[j]);
  40.             maxuj[i][j] = max(maxuj[i][j - 1], h[j]);
  41.         }
  42.     }
  43. }
  44.  
  45. const int N = 1024 * 2;
  46. int tree[NMAX][2 * N][2];
  47.  
  48. void upd(int v, int val, int t, int p){
  49.     v += N;
  50.     tree[p][v][t] = min(tree[p][v][t], val);
  51.     v >>= 1;
  52.  
  53.     while(v){
  54.         tree[p][v][t] = min(tree[p][2 * v][t], tree[p][2 * v + 1][t]);
  55.         v >>= 1;
  56.     }
  57. }
  58.  
  59. int query(int l, int r, int p, int t){
  60.     l += N;
  61.     r += N;
  62.     int wyn = INF;
  63.  
  64.     while(l <= r){
  65.         if(l & 1){
  66.             wyn = min(wyn, tree[p][l][t]);
  67.             l++;
  68.         }
  69.         if(!(r & 1)){
  70.             wyn = min(wyn, tree[p][r][t]);
  71.             r--;
  72.         }
  73.         l >>= 1;
  74.         r >>= 1;
  75.     }
  76.  
  77.     return wyn;
  78. }
  79.  
  80. pii znajdz(int start, int mn, int mx, int n){
  81.     int l = 1, r = start;
  82.  
  83.     while(l < r){
  84.         int mid = (l + r) >> 1;
  85.         if(minuj[mid][start] >= mn && maxuj[mid][start] <= mx)
  86.             r = mid;
  87.         else
  88.             l = mid + 1;
  89.     }
  90.  
  91.     int L = l;
  92.  
  93.     l = start;
  94.     r = n;
  95.  
  96.     while(l < r){
  97.         int mid = (l + r + 1) >> 1;
  98.         if(minuj[start][mid] >= mn && maxuj[start][mid] <= mx)
  99.             l = mid;
  100.         else
  101.             r = mid - 1;
  102.     }
  103.  
  104.     return {L, l};
  105. }
  106.  
  107. int main(){
  108.     ios_base::sync_with_stdio(0);
  109.     cin.tie(0);
  110.  
  111.     int n, k;
  112.     cin >> n >> k;
  113.  
  114.     vi h(n + 1);
  115.     for(int i = 1; i <= n; i++){
  116.         cin >> h[i];
  117.         minuj[i][i] = h[i];
  118.         maxuj[i][i] = h[i];
  119.     }
  120.  
  121.     build(h);
  122.  
  123.     for(int z = 0; z < NMAX; z++){
  124.         for(int i = 1; i < 2 * N; i++){
  125.             tree[z][i][0] = INF;
  126.             tree[z][i][1] = INF;
  127.         }
  128.     }
  129.  
  130.     vector<ruter> rut(k);
  131.  
  132.     for(int i = 0; i < k; i++){
  133.         cin >> rut[i].p >> rut[i].c >> rut[i].a >> rut[i].b;
  134.         rut[i].ind = i;
  135.     }
  136.  
  137.     sort(rut.begin(), rut.end(), cmp1);
  138.  
  139.     vector<stan> stany;
  140.  
  141.     for(int i = 0; i < k; i++){
  142.         for(int j = 0; j < k; j++){
  143.             if(rut[i].a <= rut[j].a && rut[i].b <= rut[j].b){
  144.                 stany.pb({i, j, rut[j].b - rut[i].a});
  145.             }
  146.         }
  147.     }
  148.  
  149.     sort(stany.begin(), stany.end(), cmp2);
  150.  
  151.     for(int i = 0; i < NMAX; i++){
  152.         for(int j = 0; j < NMAX; j++){
  153.             dp[i][j] = INF;
  154.         }
  155.     }
  156.  
  157.     for(stan st : stany){
  158.         int i = st.i;
  159.         int j = st.j;
  160.  
  161.         int lewy = rut[i].a;
  162.         int prawy = rut[j].b;
  163.  
  164.         pii prz = znajdz(rut[i].p, lewy, prawy, n);
  165.  
  166.         if(prz.ff > rut[j].p || prz.ss < rut[j].p) continue;
  167.  
  168.         if(prz.ff == 1 && prz.ss == n){
  169.             dp[i][j] = 0;
  170.         }else{
  171.             int l = 0, r = k;
  172.  
  173.             while(l < r){
  174.                 int mid = (l + r) >> 1;
  175.                 if(rut[mid].p >= prz.ff)
  176.                     r = mid;
  177.                 else
  178.                     l = mid + 1;
  179.             }
  180.  
  181.             int L = l;
  182.  
  183.             l = 0;
  184.             r = k;
  185.  
  186.             while(l < r){
  187.                 int mid = (l + r) >> 1;
  188.                 if(rut[mid].p <= prz.ss)
  189.                     l = mid + 1;
  190.                 else
  191.                     r = mid;
  192.             }
  193.  
  194.             int R = l - 1;
  195.  
  196.             if(L <= R){
  197.                 int x = query(L, R, j, 0);
  198.                 int y = query(L, R, i, 1);
  199.  
  200.                 dp[i][j] = min(dp[i][j], min(x, y));
  201.             }
  202.         }
  203.  
  204.         if(dp[i][j] != INF){
  205.             upd(i, dp[i][j] + rut[i].c, 0, j);
  206.             upd(j, dp[i][j] + rut[j].c, 1, i);
  207.  
  208.                    if(dp[i][j] != INF){
  209.             upd(i, dp[i][j] + rut[i].c, 0, j);
  210.             upd(j, dp[i][j] + rut[j].c, 1, i);
  211.  
  212.             if(i == j){
  213.                 for(int z = 0; z < k; z++){
  214.                     if(rut[i].b > rut[z].b){
  215.                         upd(i, dp[i][i] + rut[i].c, 0, z);
  216.                     }
  217.  
  218.                     if(rut[z].a > rut[i].a){
  219.                         upd(i, dp[i][i] + rut[i].c, 1, z);
  220.                     }
  221.  
  222.                     if(rut[z].a <= rut[i].a && rut[z].b >= rut[i].b &&
  223.                        (rut[z].a < rut[i].a || rut[z].b > rut[i].b) &&
  224.                        dp[z][z] != INF &&
  225.                        prz.ff <= rut[z].p && rut[z].p <= prz.ss){
  226.                         dp[i][i] = min(dp[i][i], dp[z][z] + rut[z].c);
  227.                     }
  228.                 }
  229.             }
  230.         }
  231.         }
  232.     }
  233.  
  234.     vi ans(k);
  235.  
  236.     for(int i = 0; i < k; i++){
  237.         int ind = rut[i].ind;
  238.  
  239.         if(h[rut[i].p] < rut[i].a || h[rut[i].p] > rut[i].b){
  240.             ans[ind] = -1;
  241.         }else if(dp[i][i] == INF){
  242.             ans[ind] = -1;
  243.         }else{
  244.             ans[ind] = dp[i][i] + rut[i].c;
  245.         }
  246.     }
  247.  
  248.     for(int x : ans) cout << x << "\n";
  249.  
  250.     return 0;
  251. }
Success #stdin #stdout 0.02s 86484KB
comments (?)
stdin
copy 
7 8
4 2 3 1 5 6 7
3 1 2 4
1 2 1 3
4 4 1 7
6 10 1 7
6 20 6 6
6 30 5 5
7 40 1 6
7 50 7 7
stdout
copy 
7
-1
4
10
30
-1
-1
90
https://ideone.com/RlmcdI
language:
C++ (gcc 8.3)
created:
2 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!