oj.uz

답안 #345976

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
345976 2021-01-08T20:01:19 Z Ruxandra985 Election (BOI18_election) C++14
82 / 100
 3000 ms 162016 KB 
#include <bits/stdc++.h>
#define DIMN 500010
using namespace std;
int vi[DIMN] , sp[DIMN] , tt[DIMN] , next_c[DIMN];
map <int , int> mp;
pair <int , int> rmq[20][DIMN];
int srmq[20][DIMN];
vector <int> v[DIMN];
 
int aint[4 * DIMN];
int sol;
 
void build (int nod ,int st,int dr){
    int mid = (st + dr)/2;
    if (st == dr){
 
        aint[nod] = min(0 , vi[st]);
 
        return;
    }
 
    build (2*nod,st,mid);
    build (2*nod+1,mid+1,dr);
 
    aint[nod] = min(aint[2 * nod + 1] , sp[dr] - sp[mid] + aint[2 * nod]);
 
}
 
void query (int nod , int st , int dr , int l , int r){
    int mid = (st + dr)/2;
 
    if (l <= st && dr <= r){ /// sunt in interval bun
        sol = min(sol , aint[nod] + sp[r] - sp[dr]);
 
    }
    else {
 
        if (mid + 1 <= r)
            query(2 * nod + 1 , mid + 1 , dr , l , r);
 
        if (l <= mid)
            query(2 * nod , st , mid , l , r);
 
 
    }
 
 
}
 
int main()
{
    FILE *fin = stdin;
    //FILE *ans = fopen ("idk.in","r");
    FILE *fout = stdout;
    int n, q , i , l , r , nod , j , vecin , maxi , fth , inc = 0;
    char c;
    fscanf (fin,"%d\n",&n);
    for (i = 1 ; i <= n ; i++){
        c=fgetc (fin);
        if (c == 'C')
            vi[i] = 1;
        else vi[i] = -1;
 
        sp[i] = vi[i] + sp[i - 1];
 
    }
    next_c[n + 1] = n + 1;
    for (i = n ; i ; i--){
        if (vi[i] == 1)
            next_c[i] = i;
        else next_c[i] = next_c[i + 1];
    }
 
    for (i = n ; i ; i--){
 
        /// sp[j] - sp[i - 1] = -1
        /// sp[j] = -1 + sp[i - 1]
 
        if (vi[i] == -1){
 
            v[i + 1].push_back(i);
            tt[i] = i + 1;
 
        }
        else {
 
            if (mp[sp[i - 1] - 1] != 0){
                v[mp[sp[i - 1] - 1]].push_back(i); /// intervalul i...chestie are suma -1
                tt[i] = mp[sp[i - 1] - 1];
            }
            else {
                v[n + 1].push_back(i); /// n + 1 = nod fictiv radacina
                tt[i] = n + 1;
            }
 
        }
 
        mp[sp[i]] = i;
 
    }
 
    build (1 , 1 , n);
 
    /// vezi ce valoare dai muchiilor
 
    for (nod = 1 ; nod <= n + 1 ; nod++){ /// nod este tatal
 
        for (j = 0 ; j < v[nod].size() ; j++){
 
            vecin = v[nod][j];
 
            //printf ("%d %d " , vecin , nod);
 
            if (nod - vecin > 1 || (nod - vecin == 1 && vi[nod] == -1))
                srmq[0][vecin] = 1; /// altfel e 0
 
            if (nod - vecin == 1 && vi[vecin] == -1){
 
                rmq[0][vecin] = make_pair(nod , 0);
                //printf ("%d\n", 0);
                continue;
 
            }
 
            sol = DIMN;
            query(1 , 1 , n , vecin , min(n , nod));
 
            if (nod != n + 1){
                rmq[0][vecin] = make_pair(nod , -sol - 1);
                //printf ("%d\n", -sol - 1);
            }
            else {
                rmq[0][vecin] = make_pair(nod , -sol);
                //printf ("%d\n",-sol);
            }
 
        }
 
    }
 
    for (i = 1 ; i < 20 ; i++){
        for (j = 1 ; j <= n ; j++){
 
 
            rmq[i][j].first = rmq[i - 1][rmq[i - 1][j].first].first;
            rmq[i][j].second = max(rmq[i - 1][j].second , rmq[i - 1][rmq[i - 1][j].first].second);
            srmq[i][j] = srmq[i - 1][j] + srmq[i - 1][rmq[i - 1][j].first];
 
        }
    }
 
 
 
    fscanf (fin,"%d",&q);
 
    int correct , mini = DIMN , li , ri;
    int deadd = 0 , ant;
 
    for (int aux = 1 ; aux <= q ; aux++){
 
        fscanf (fin,"%d%d",&l,&r);
 
        /*if (aux == 1597){
            printf ("\n");
            for (int k = l ; k <= r ; k++)
                printf ("%d ", vi[k]);
            printf ("\n");
            printf ("a");
        }*/
 
        li = l;
        ri = r;
 
        maxi = 0;
 
        //if (vi[li] == 1)
        inc = 0;
        //else inc = 0;
        l = next_c[l];
 
        if (l > r){
            deadd = ri - li + 1;
            inc = maxi = 0;
        }
        else {
            deadd = l - li;
 
            while (tt[l] <= r){
 
                if (srmq[0][l]){
                    if (l + 1 != tt[l])
                        maxi = max(maxi - (sp[tt[l] - 1] - sp[l - 1]) , rmq[0][l].second);
                }
                //else {
                  //  maxi = max(maxi - 1 , 0);
                //}
                inc += srmq[0][l];
 
                //printf ("%d ",maxi);
 
                ant = srmq[0][l];
 
                l = tt[l];
 
            }
 
            /*maxi = 0;
            inc = -1;
            for (i = 19 ; i >= 0 ; i--){
 
                fth = rmq[i][l].first;
                if (fth  < r && fth){
                    maxi = max(maxi , rmq[i][l].second);
                    l = fth;
                    inc += (1 << i);
                }
 
            }*/
 
            /// l e < r
 
            if (ant)
                l++;
 
            if (l <= r){
                sol = DIMN;
                query (1 , 1 , n , l , r);
                maxi = max(maxi - ( sp[r] - sp[l - 1] ) , -sol);
            }
 
        }
 
        //fscanf (ans, "%d",&correct);
 
        //maxi = max(maxi , - (sp[ri] - sp[li - 1] + inc));
 
        /*if (correct != inc + maxi + deadd){
            mini = min(mini , ri - li + 1);
            if (ri - li + 1 == 4)
                printf ("%d\n",aux);
        }*/
 
        fprintf (fout,"%d\n",inc + maxi + deadd);
 
    }
    //printf ("%d",mini);
    return 0;
}

Compilation message

election.cpp: In function 'int main()':
election.cpp:108:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  108 |         for (j = 0 ; j < v[nod].size() ; j++){
      |                      ~~^~~~~~~~~~~~~~~
election.cpp:55:53: warning: unused variable 'fth' [-Wunused-variable]
   55 |     int n, q , i , l , r , nod , j , vecin , maxi , fth , inc = 0;
      |                                                     ^~~
election.cpp:156:9: warning: unused variable 'correct' [-Wunused-variable]
  156 |     int correct , mini = DIMN , li , ri;
      |         ^~~~~~~
election.cpp:156:19: warning: unused variable 'mini' [-Wunused-variable]
  156 |     int correct , mini = DIMN , li , ri;
      |                   ^~~~
election.cpp:57:12: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   57 |     fscanf (fin,"%d\n",&n);
      |     ~~~~~~~^~~~~~~~~~~~~~~
election.cpp:154:12: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  154 |     fscanf (fin,"%d",&q);
      |     ~~~~~~~^~~~~~~~~~~~~
election.cpp:161:16: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  161 |         fscanf (fin,"%d%d",&l,&r);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~
election.cpp:222:13: warning: 'ant' may be used uninitialized in this function [-Wmaybe-uninitialized]
  222 |             if (ant)
      |             ^~

Subtask #1
28.0 / 28.0

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 13036 KB Output is correct
2 Correct 11 ms 13036 KB Output is correct
3 Correct 11 ms 13036 KB Output is correct
4 Correct 11 ms 13036 KB Output is correct
5 Correct 11 ms 13036 KB Output is correct

Subtask #2
54.0 / 54.0

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 13036 KB Output is correct
2 Correct 11 ms 13036 KB Output is correct
3 Correct 11 ms 13036 KB Output is correct
4 Correct 11 ms 13036 KB Output is correct
5 Correct 11 ms 13036 KB Output is correct
6 Correct 158 ms 33516 KB Output is correct
7 Correct 154 ms 33260 KB Output is correct
8 Correct 105 ms 33260 KB Output is correct
9 Correct 98 ms 33260 KB Output is correct
10 Correct 97 ms 33900 KB Output is correct
11 Correct 1677 ms 34528 KB Output is correct
12 Correct 393 ms 33772 KB Output is correct
13 Correct 1066 ms 35232 KB Output is correct
14 Correct 328 ms 34156 KB Output is correct
15 Correct 125 ms 34284 KB Output is correct

Subtask #3
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 13036 KB Output is correct
2 Correct 11 ms 13036 KB Output is correct
3 Correct 11 ms 13036 KB Output is correct
4 Correct 11 ms 13036 KB Output is correct
5 Correct 11 ms 13036 KB Output is correct
6 Correct 158 ms 33516 KB Output is correct
7 Correct 154 ms 33260 KB Output is correct
8 Correct 105 ms 33260 KB Output is correct
9 Correct 98 ms 33260 KB Output is correct
10 Correct 97 ms 33900 KB Output is correct
11 Correct 1677 ms 34528 KB Output is correct
12 Correct 393 ms 33772 KB Output is correct
13 Correct 1066 ms 35232 KB Output is correct
14 Correct 328 ms 34156 KB Output is correct
15 Correct 125 ms 34284 KB Output is correct
16 Correct 1901 ms 159340 KB Output is correct
17 Correct 749 ms 158956 KB Output is correct
18 Correct 1394 ms 159340 KB Output is correct
19 Correct 1506 ms 158828 KB Output is correct
20 Correct 889 ms 162016 KB Output is correct
21 Execution timed out 3093 ms 156808 KB Time limit exceeded
22 Halted 0 ms 0 KB -