oj.uz

Submission #251474

# Submission time Handle Problem Language Result Execution time Memory
251474 2020-07-21T10:51:00 Z casperwang Lollipop (POI11_liz) C++14
25 / 100
 540 ms 26712 KB 
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 2000000;
int n, q;
int k, l, r;
int L, R;
string s;
int a[MAXN+1];
int pre[MAXN+1];
int suf[MAXN+2];

signed main() {
  ios_base::sync_with_stdio(0), cin.tie(0);
  cin >> n >> q;
  cin >> s;
  for (int i = 0; i < s.size(); i++)
    a[i+1] = (s[i] == 'T' ? 2 : 1);
  for (int i = 1; i <= n; i++)
    pre[i] = pre[i-1] + a[i], R = (a[i] == 1 ? i : R);
  for (int i = n; i >= 1; i--)
    suf[n-i+1] = suf[n-i] + a[i], L = (a[i] == 1 ? n-i+1 : L);
  for (int i = 0; i < q; i++) {
    cin >> k;
    if (pre[R] >= k) {
      l = lower_bound(pre, pre+n+1, pre[R]-k) - pre;
      if (pre[R] - pre[l] < k) l--;
      r = (pre[R] - pre[l] == k ? R : R-1);
      l++;
      cout << l << " " << r << "\n";
    } else if (suf[L] >= k) {
      r = lower_bound(suf, suf+n+1, suf[L]-k) - suf;
      if (suf[L] - suf[r] < k) r--;
      l = (suf[L] - suf[r] == k ? L : L-1);
      r++;
      cout << n+1-l << " " << n+1-r << "\n";
    } else if (pre[n] <= k) {
      cout << "NIE\n";
    } else {
      l = lower_bound(pre, pre+n+1, pre[n]-k) - pre;
      if (pre[n] - pre[l] != k)
        cout << "NIE\n";
      else
        cout << l+1 << " " << n << "\n";
    }
  }
}

Compilation message

liz.cpp: In function 'int main()':
liz.cpp:17:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0; i < s.size(); i++)
                   ~~^~~~~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Incorrect 0 ms 384 KB Oczekiwano przedzial, otrzymano 'NIE'

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Incorrect 7 ms 512 KB Oczekiwano przedzial, otrzymano 'NIE'

Subtask #4
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 512 KB Oczekiwano przedzial, otrzymano 'NIE'
2 Halted 0 ms 0 KB -

Subtask #5
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 896 KB Oczekiwano przedzial, otrzymano 'NIE'
2 Halted 0 ms 0 KB -

Subtask #6
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 2040 KB Output is correct
2 Correct 177 ms 5876 KB Output is correct
3 Correct 78 ms 3064 KB Output is correct

Subtask #7
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 30 ms 2168 KB Oczekiwano przedzial, otrzymano 'NIE'
2 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 133 ms 5292 KB Output is correct
2 Incorrect 108 ms 4652 KB Oczekiwano przedzial, otrzymano 'NIE'
3 Halted 0 ms 0 KB -

Subtask #9
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 284 ms 12300 KB Oczekiwano przedzial, otrzymano 'NIE'
2 Halted 0 ms 0 KB -

Subtask #10
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 253 ms 13708 KB Output is correct
2 Correct 333 ms 16652 KB Output is correct
3 Correct 379 ms 16768 KB Output is correct

Subtask #11
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 533 ms 25808 KB Output is correct
2 Incorrect 450 ms 23952 KB Oczekiwano przedzial, otrzymano 'NIE'
3 Halted 0 ms 0 KB -

Subtask #12
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 540 ms 26712 KB Oczekiwano przedzial, otrzymano 'NIE'
2 Halted 0 ms 0 KB -