QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#875250#2747. MeetingsWansur#0 1835ms4736kbC++201.2kb2025-01-29 14:07:302025-01-29 14:07:31

Judging History

This is the latest submission verdict.

  • [2025-01-29 14:07:31]
  • Judged
  • Verdict: 0
  • Time: 1835ms
  • Memory: 4736kb
  • [2025-01-29 14:07:30]
  • Submitted

answer

#include "meetings.h"
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

const int maxn = 1e6 + 12;

ll sum[maxn];
int a[maxn];
int n, m, k;

vector<long long> minimum_costs(vector<int> H, vector<int> l, vector<int> r) {
   n = (int)H.size(), m = (int)l.size();
   for(int i = 0; i < n; i++) {
      a[i] = H[i];
   }

   vector<ll> ans(m, 1e18);
   for(int i = 0; i < m; i++) {
      stack<int> s;
      s.push(l[i] - 1);
      for(int j = l[i]; j <= r[i]; j++) {
         sum[j] = sum[j - 1];
         while(s.size() > 1 && a[s.top()] < a[j]) {
            int x = s.top();
            s.pop();
            sum[j] -= (x - s.top()) * a[x];
         }
         sum[j] += a[j] * (j - s.top());
         s.push(j);
      }

      while(s.size()) {
         s.pop();
      }
      s.push(r[i] + 1);
      ll val = 0;
      for(int j = r[i]; j >= l[i]; j--) {
         while(s.size() > 1 && a[s.top()] < a[j]) {
            int x = s.top();
            s.pop();
            val -= (s.top() - x) * a[x];
         }
         val += a[j] * (s.top() - j);
         s.push(j);
         ans[i] = min(ans[i], val + sum[j] - a[j]);
         sum[j] = 0;
      }
   }
   return ans;
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 4
Accepted
time: 0ms
memory: 3840kb

input:

1 1
877914575
0 0

output:

877914575

result:

ok single line: '877914575'

Test #2:

score: 0
Wrong Answer
time: 0ms
memory: 3968kb

input:

3000 10
24979445 861648772 623690081 433933447 476190629 262703497 211047202 971407775 628894325 731963982 822804784 450968417 430302156 982631932 161735902 880895728 923078537 707723857 189330739 910286918 802329211 404539679 303238506 317063340 492686568 773361868 125660016 650287940 839296263 462...

output:

-8646157031
-8530536131
-8741415114
-5079631347
-12256370192
-9922651419
-8819069008
-9207392210
-9876007810
-12029301577

result:

wrong answer 1st lines differ - expected: '1024247893897', found: '-8646157031'

Subtask #2:

score: 0
Skipped

Dependency #1:

0%

Subtask #3:

score: 0
Time Limit Exceeded

Test #16:

score: 17
Accepted
time: 0ms
memory: 3840kb

input:

1 1
2
0 0

output:

2

result:

ok single line: '2'

Test #17:

score: 17
Accepted
time: 1835ms
memory: 4736kb

input:

8014 48643
2 2 1 2 2 1 2 1 1 1 1 1 2 2 1 1 2 1 2 2 1 2 1 1 2 2 2 1 2 1 1 2 1 1 2 1 2 2 1 1 2 2 2 1 1 1 1 2 2 1 1 1 1 1 2 2 2 2 2 2 1 1 2 2 2 1 1 2 1 1 2 2 2 1 2 2 1 1 2 1 1 1 2 1 1 1 1 1 2 2 1 1 2 1 2 2 2 2 2 2 1 2 2 1 2 2 2 1 1 2 1 2 2 1 2 1 1 2 2 2 2 2 2 1 2 2 1 1 1 2 1 1 1 1 2 1 2 2 1 1 1 1 1 1 2...

output:

3556
2463
7389
1531
8055
565
9221
4957
4500
11001
4663
6013
10655
426
331
1495
3961
2197
3543
2786
773
13953
13077
6111
9863
7113
1576
12305
9019
9511
1019
10123
412
8015
13491
9367
7363
2001
5417
8827
361
815
5863
4607
173
6827
5345
5214
3430
2512
11655
3621
9051
290
583
4363
4694
2789
2865
613
464...

result:

ok 48643 lines

Test #18:

score: 0
Time Limit Exceeded

input:

100000 100000
1 2 1 1 2 1 1 2 2 2 2 1 1 1 2 2 1 1 2 2 2 1 1 2 2 1 2 2 1 2 2 1 1 1 2 2 1 2 2 2 1 1 1 1 1 2 2 2 2 2 1 1 2 2 2 2 2 1 2 1 1 1 1 1 1 2 1 1 1 1 1 2 1 1 2 2 1 1 1 2 2 1 1 1 2 2 2 2 2 1 1 1 1 2 2 1 1 1 1 1 2 2 1 2 1 2 1 2 2 2 2 2 2 2 1 1 1 1 2 2 2 1 1 2 1 1 1 1 2 2 2 1 1 1 2 2 2 1 1 2 2 1 2 ...

output:

Unauthorized output

result:


Subtask #4:

score: 0
Skipped

Dependency #3:

0%

Subtask #5:

score: 0
Skipped

Dependency #1:

0%