fork(1) 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) r = mid;
  86.         else l = mid + 1;
  87.     }
  88.  
  89.     int L = l;
  90.  
  91.     l = start;
  92.     r = n;
  93.  
  94.     while(l < r){
  95.         int mid = (l + r + 1) >> 1;
  96.         if(minuj[start][mid] >= mn && maxuj[start][mid] <= mx) l = mid;
  97.         else r = mid - 1;
  98.     }
  99.  
  100.     return {L, l};
  101. }
  102.  
  103. int main(){
  104.     ios_base::sync_with_stdio(0);
  105.     cin.tie(0);
  106.  
  107.     int n, k;
  108.     cin >> n >> k;
  109.  
  110.     vi h(n + 1);
  111.     for(int i = 1; i <= n; i++){
  112.         cin >> h[i];
  113.         minuj[i][i] = h[i];
  114.         maxuj[i][i] = h[i];
  115.     }
  116.  
  117.     build(h);
  118.  
  119.     for(int z = 0; z < NMAX; z++){
  120.         for(int i = 1; i < 2 * N; i++){
  121.             tree[z][i][0] = INF;
  122.             tree[z][i][1] = INF;
  123.         }
  124.     }
  125.  
  126.     vector<ruter> rut(k);
  127.  
  128.     for(int i = 0; i < k; i++){
  129.         cin >> rut[i].p >> rut[i].c >> rut[i].a >> rut[i].b;
  130.         rut[i].ind = i;
  131.     }
  132.  
  133.     sort(rut.begin(), rut.end(), cmp1);
  134.  
  135.     vector<stan> stany;
  136.  
  137.     for(int i = 0; i < k; i++){
  138.         for(int j = 0; j < k; j++){
  139.             if(rut[i].a <= rut[j].a && rut[i].b <= rut[j].b){
  140.                 stany.pb({i, j, rut[j].b - rut[i].a});
  141.             }
  142.         }
  143.     }
  144.  
  145.     sort(stany.begin(), stany.end(), cmp2);
  146.  
  147.     for(int i = 0; i < NMAX; i++){
  148.         for(int j = 0; j < NMAX; j++){
  149.             dp[i][j] = INF;
  150.         }
  151.     }
  152.  
  153.     for(stan st : stany){
  154.         int i = st.i;
  155.         int j = st.j;
  156.  
  157.         int lewy = rut[i].a;
  158.         int prawy = rut[j].b;
  159.  
  160.         pii prz = znajdz(rut[i].p, lewy, prawy, n);
  161.  
  162.         if(prz.ff > rut[j].p || prz.ss < rut[j].p)
  163.             continue;
  164.  
  165.         if(prz.ff == 1 && prz.ss == n){
  166.             dp[i][j] = 0;
  167.         }
  168.         else{
  169.             int l = 0, r = k;
  170.  
  171.             while(l < r){
  172.                 int mid = (l + r) >> 1;
  173.                 if(rut[mid].p >= prz.ff)
  174.                     r = mid;
  175.                 else
  176.                     l = mid + 1;
  177.             }
  178.  
  179.             int L = l;
  180.  
  181.             l = 0;
  182.             r = k;
  183.  
  184.             while(l < r){
  185.                 int mid = (l + r) >> 1;
  186.                 if(rut[mid].p <= prz.ss)
  187.                     l = mid + 1;
  188.                 else
  189.                     r = mid;
  190.             }
  191.  
  192.             int R = l - 1;
  193.  
  194.             if(L <= R){
  195.                 int x = query(L, R, j, 0);
  196.                 int y = query(L, R, i, 1);
  197.  
  198.                 dp[i][j] = min(dp[i][j], min(x, y));
  199.             }
  200.         }
  201.  
  202.         if(dp[i][j] != INF){
  203.             upd(i, dp[i][j] + rut[i].c, 0, j);
  204.             upd(j, dp[i][j] + rut[j].c, 1, i);
  205.  
  206.             if(i == j){
  207.                 for(int z = 0; z < k; z++){
  208.                     if(rut[i].b > rut[z].b){
  209.                         upd(i, dp[i][i] + rut[i].c, 0, z);
  210.                     }
  211.                 }
  212.             }
  213.         }
  214.     }
  215.  
  216.     vi ans(k);
  217.  
  218.     for(int i = 0; i < k; i++){
  219.         int ind = rut[i].ind;
  220.  
  221.         if(h[rut[i].p] < rut[i].a || h[rut[i].p] > rut[i].b){
  222.             ans[ind] = -1;
  223.         }else if(dp[i][i] == INF){
  224.             ans[ind] = -1;
  225.         }else{
  226.             ans[ind] = dp[i][i] + rut[i].c;
  227.         }
  228.     }
  229.  
  230.     for(int x : ans)
  231.         cout << x << "\n";
  232.  
  233.     return 0;
  234. }
Success #stdin #stdout 0.02s 86068KB
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/m4R0mq
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!