Submission #26722

#	Time	Username	Problem	Language	Result	Execution time	Memory
26722		model_code	Untitled (POI11_tem)	C++11	100 / 100	369 ms	12604 KiB

Main

/*************************************************************************
 *                                                                       *
 *                    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 / 8
• Subtask 2: 8 / 8
• Subtask 3: 8 / 8
• Subtask 4: 8 / 8
• Subtask 5: 8 / 8
• Subtask 6: 8 / 8
• Subtask 7: 8 / 8
• Subtask 8: 8 / 8
• Subtask 9: 9 / 9
• Subtask 10: 9 / 9
• Subtask 11: 9 / 9
• Subtask 12: 9 / 9