Submission #1690620
Source Code Expand
#include <bits/stdc++.h> #define rep(i, a, n) for(int i = a; i < n; i++) #define REP(i, n) rep(i, 0, n) #define repb(i, a, b) for(int i = a; i >= b; i--) #define all(a) a.begin(), a.end() #define int long long #define chmax(x, y) x = max(x, y) #define chmin(x, y) x = min(x, y) using namespace std; typedef pair<int, int> P; const int mod = 1000000007; const int INF = 1e12; //RMQ struct SegTree2 { int N; vector<int> dat; SegTree2() {} SegTree2(int n) { N = 1; while(N < n) N *= 2; dat.resize(2 * N, -1); // for(int i = 0; i < 2*N-1; i++) // dat[i] = INF; } // update k th element void update(int k, int a) { k += N-1; // leaf dat[k] = a; while(k > 0) { k = (k - 1) / 2; dat[k] = max(dat[k*2+1], dat[k*2+2]); } } // min [a, b) int query(int a, int b) { return query(a, b, 0, 0, N); } int query(int a, int b, int k, int l, int r) { if(r <= a or b <= l) return -1; if(a <= l and r <= b) return dat[k]; int m = (l + r) / 2; return max(query(a, b, k*2+1, l, m), query(a, b, k*2+2, m, r)); } }; signed main(){ ios::sync_with_stdio(false); cin.tie(0); int n; cin >> n; vector<int> a(n); SegTree2 r(n); rep(i, 0, n){ cin >> a[i]; r.update(i, a[i]); } string s; cin >> s; int cnt = 0; rep(i, 0, s.size()) if(s[i] == 'M') cnt++; rep(i, 0, n - cnt){ a[i] = r.query(i, i + cnt + 1); } int ans = INF; rep(i, 0, n - cnt){ chmin(ans, a[i]); } cout << ans << endl; }
Submission Info
Submission Time | |
---|---|
Task | B - Compression |
User | treeone |
Language | C++14 (GCC 5.4.1) |
Score | 400 |
Code Size | 1706 Byte |
Status | WA |
Exec Time | 32 ms |
Memory | 3456 KB |
Judge Result
Set Name | Sample | subtask1 | subtask2 | All | ||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 400 / 400 | 0 / 800 | 0 / 200 | ||||||||||||||
Status |
|
|
|
|
Set Name | Test Cases |
---|---|
Sample | sample_1.txt, sample_2.txt, sample_3.txt, sample_4.txt |
subtask1 | sample_2.txt, subtask_1.2_1.txt, subtask_1.2_2.txt, subtask_1_1.txt, subtask_1_10.txt, subtask_1_2.txt, subtask_1_3.txt, subtask_1_4.txt, subtask_1_5.txt, subtask_1_6.txt, subtask_1_7.txt, subtask_1_8.txt, subtask_1_9.txt |
subtask2 | sample_1.txt, subtask_1.2_1.txt, subtask_1.2_2.txt, subtask_2_1.txt, subtask_2_10.txt, subtask_2_2.txt, subtask_2_3.txt, subtask_2_4.txt, subtask_2_5.txt, subtask_2_6.txt, subtask_2_7.txt, subtask_2_8.txt, subtask_2_9.txt |
All | sample_1.txt, sample_2.txt, sample_3.txt, sample_4.txt, 2_1.txt, 2_2.txt, sample_1.txt, sample_2.txt, sample_3.txt, sample_4.txt, subtask_1.2_1.txt, subtask_1.2_2.txt, subtask_1_1.txt, subtask_1_10.txt, subtask_1_2.txt, subtask_1_3.txt, subtask_1_4.txt, subtask_1_5.txt, subtask_1_6.txt, subtask_1_7.txt, subtask_1_8.txt, subtask_1_9.txt, subtask_2_1.txt, subtask_2_10.txt, subtask_2_2.txt, subtask_2_3.txt, subtask_2_4.txt, subtask_2_5.txt, subtask_2_6.txt, subtask_2_7.txt, subtask_2_8.txt, subtask_2_9.txt, subtask_3_1.txt, subtask_3_10.txt, subtask_3_11.txt, subtask_3_12.txt, subtask_3_13.txt, subtask_3_14.txt, subtask_3_15.txt, subtask_3_16.txt, subtask_3_17.txt, subtask_3_18.txt, subtask_3_19.txt, subtask_3_2.txt, subtask_3_20.txt, subtask_3_21.txt, subtask_3_3.txt, subtask_3_4.txt, subtask_3_5.txt, subtask_3_6.txt, subtask_3_7.txt, subtask_3_8.txt, subtask_3_9.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
2_1.txt | AC | 2 ms | 256 KB |
2_2.txt | AC | 1 ms | 256 KB |
sample_1.txt | AC | 1 ms | 256 KB |
sample_2.txt | AC | 1 ms | 256 KB |
sample_3.txt | WA | 2 ms | 256 KB |
sample_4.txt | WA | 1 ms | 256 KB |
subtask_1.2_1.txt | AC | 2 ms | 256 KB |
subtask_1.2_2.txt | AC | 1 ms | 256 KB |
subtask_1_1.txt | AC | 32 ms | 3328 KB |
subtask_1_10.txt | AC | 24 ms | 3328 KB |
subtask_1_2.txt | AC | 18 ms | 3328 KB |
subtask_1_3.txt | AC | 16 ms | 3328 KB |
subtask_1_4.txt | AC | 19 ms | 3200 KB |
subtask_1_5.txt | AC | 5 ms | 640 KB |
subtask_1_6.txt | AC | 29 ms | 3328 KB |
subtask_1_7.txt | AC | 1 ms | 256 KB |
subtask_1_8.txt | AC | 25 ms | 3328 KB |
subtask_1_9.txt | AC | 24 ms | 3328 KB |
subtask_2_1.txt | WA | 25 ms | 3328 KB |
subtask_2_10.txt | WA | 25 ms | 3328 KB |
subtask_2_2.txt | WA | 25 ms | 3328 KB |
subtask_2_3.txt | WA | 25 ms | 3456 KB |
subtask_2_4.txt | WA | 25 ms | 3328 KB |
subtask_2_5.txt | AC | 1 ms | 256 KB |
subtask_2_6.txt | AC | 1 ms | 256 KB |
subtask_2_7.txt | AC | 1 ms | 256 KB |
subtask_2_8.txt | WA | 25 ms | 3328 KB |
subtask_2_9.txt | WA | 7 ms | 1024 KB |
subtask_3_1.txt | WA | 25 ms | 3328 KB |
subtask_3_10.txt | WA | 25 ms | 3328 KB |
subtask_3_11.txt | WA | 25 ms | 3328 KB |
subtask_3_12.txt | WA | 30 ms | 3328 KB |
subtask_3_13.txt | WA | 30 ms | 3328 KB |
subtask_3_14.txt | WA | 30 ms | 3328 KB |
subtask_3_15.txt | WA | 32 ms | 3328 KB |
subtask_3_16.txt | WA | 32 ms | 3328 KB |
subtask_3_17.txt | AC | 17 ms | 3328 KB |
subtask_3_18.txt | AC | 17 ms | 3328 KB |
subtask_3_19.txt | AC | 19 ms | 3328 KB |
subtask_3_2.txt | WA | 25 ms | 3456 KB |
subtask_3_20.txt | AC | 20 ms | 3328 KB |
subtask_3_21.txt | AC | 19 ms | 3328 KB |
subtask_3_3.txt | WA | 4 ms | 640 KB |
subtask_3_4.txt | WA | 24 ms | 3200 KB |
subtask_3_5.txt | WA | 21 ms | 3200 KB |
subtask_3_6.txt | WA | 25 ms | 3328 KB |
subtask_3_7.txt | WA | 25 ms | 3328 KB |
subtask_3_8.txt | WA | 25 ms | 3328 KB |
subtask_3_9.txt | WA | 25 ms | 3328 KB |