oj.uz

Submission #26722

# Submission time Handle Problem Language Result Execution time Memory
26722 2017-07-05T10:25:41 Z model_code Temperature (POI11_tem) C++11
100 / 100
 369 ms 12604 KB 
/*************************************************************************
 *                                                                       *
 *                    XVIII Olimpiada Informatyczna                      *
 *                                                                       *
 *   Zadanie:           Temperatura                                      *
 *   Autor:             Bartlomiej Wolowiec                              *
 *   Zlozonosc czasowa: O(n)                                             *
 *   Opis:              Rozwiazanie wzorcowe                             *
 *                                                                       *
 *************************************************************************/

/* - */
#include <iostream>
#include <algorithm>
#include <queue>
#include <cstdio>
#define PII pair<int, int>
using namespace std;
/* * */

#define MAX_N 1000000
int Tmin[MAX_N];
int Tmax[MAX_N];


#define TEMP second
#define POZ first

int main(void){
    int n, wynik=0;

    if (scanf("%i", &n) != 1) return 1;
    for(int i=0; i<n; i++)
        if(scanf("%i%i", &Tmin[i], &Tmax[i]) != 2) return 1;

    deque<PII> Q;
    for(int i=0; i<n; i++){
        int a=Tmin[i], b=Tmax[i];
        int naj = i;
        while(!Q.empty() && Q.front().TEMP <= a){
            naj = min(naj, Q.front().POZ);
            Q.pop_front();
        }
        Q.push_front(PII(naj, a));
        while(!Q.empty() && Q.back().TEMP > b){
            wynik = max(wynik, i-Q.back().POZ);
            Q.pop_back();
        }
    }
    while(!Q.empty()){
        wynik = max(wynik, n-Q.back().POZ);
        Q.pop_back();
    }
    printf("%i\n", wynik);
    return 0;
}

Subtask #1
8.0 / 8.0

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

Subtask #2
8.0 / 8.0

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

Subtask #3
8.0 / 8.0

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

Subtask #4
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 103 ms 9832 KB Output is correct
2 Correct 126 ms 9832 KB Output is correct
3 Correct 136 ms 9832 KB Output is correct

Subtask #5
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 226 ms 9832 KB Output is correct
2 Correct 233 ms 9832 KB Output is correct
3 Correct 276 ms 11676 KB Output is correct

Subtask #6
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 296 ms 9832 KB Output is correct
2 Correct 239 ms 9832 KB Output is correct
3 Correct 346 ms 12076 KB Output is correct

Subtask #7
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 353 ms 9832 KB Output is correct
2 Correct 236 ms 9832 KB Output is correct
3 Correct 349 ms 12604 KB Output is correct

Subtask #8
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 286 ms 10360 KB Output is correct
2 Correct 196 ms 10352 KB Output is correct
3 Correct 283 ms 9832 KB Output is correct

Subtask #9
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 166 ms 9832 KB Output is correct
2 Correct 153 ms 9832 KB Output is correct
3 Correct 153 ms 9832 KB Output is correct

Subtask #10
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 169 ms 9832 KB Output is correct
2 Correct 156 ms 9832 KB Output is correct

Subtask #11
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 323 ms 9832 KB Output is correct
2 Correct 369 ms 12472 KB Output is correct

Subtask #12
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 313 ms 9832 KB Output is correct
2 Correct 326 ms 12208 KB Output is correct