# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
222377 | cheeheng | Grudanje (COCI19_grudanje) | C++14 | 2094 ms | 12664 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
char S[100005];
int ft[28][100005];
int N, Q;
int a[100005];
int b[100005];
int p[100005];
int prefixSum[28][100005];
int init(){
memset(ft, 0, sizeof(ft));
}
int rsq(int i, int b){
int sum = 0;
while(b){
sum += ft[i][b];
b -= b&(-b);
}
return sum;
}
int rsq(int i, int a, int b){
return rsq(i, b)-rsq(i, a-1);
}
void update(int i, int k, int v){
while(k <= N){
ft[i][k] += v;
k += k&(-k);
}
}
bool boleh(int k){
init();
for(int i = 0; i < N; i ++){
update(S[i]-'a', i+1, 1);
}
for(int i = 0; i < k; i ++){
update(S[p[i]-1]-'a', p[i], -1);
}
for(int i = 0; i < Q; i ++){
for(int j = 0; j < 26; j ++){
//printf("boleh(%d) %d %d %d: %d\n", k, j, a[i], b[i], rsq(j, a[i], b[i]));
if(rsq(j, a[i], b[i]) > 1){
return false;
}
}
}
return true;
}
int main(){
scanf(" %s", S);
N = strlen(S);
scanf("%d", &Q);
/*for(int i = 0; i < 26; i ++){
prefixSum[i][0] = 0;
for(int j = 1; j <= N; j ++){
prefixSum[i][j] = prefixSum[i][j-1] + (S[j-1] == ('a'+i));
}
}*/
for(int i = 0; i < Q; i ++){
scanf("%d%d", &a[i], &b[i]);
}
for(int i = 0; i < N; i ++){
scanf("%d", &p[i]);
}
// This part can be improved to binary search the answer
for(int i = 0; i <= N; i ++){
if(boleh(i)){
printf("%d", i);
return 0;
}
}
return 0;
}
컴파일 시 표준 에러 (stderr) 메시지
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |