ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила
вернуться в форум

Обсуждение задачи 1019. Перекрашивание прямой

Why WA #11 ??????
Послано The Cheater 28 июл 2004 15:39
#include <iostream>
#include <algorithm>
#include <vector>
#define MAX 5005
using namespace std;
struct type {
    int x,y;
    char c;
} a[MAX];
struct type line[MAX];
vector<int> v;
int n;
// read data
void init() {
    cin >> n;
    v.push_back(0);
    v.push_back(1000000000);
    int x,y;
    char c;
    a[0].x = 0;
    a[0].y = 1000000000;
    a[0].c = 'w';
    for(int i=1;i<=n;i++) {
        cin >> x >> y >> c;
        a[i].x = x; a[i].y = y; a[i].c = c;
        v.push_back(a[i].x); v.push_back(a[i].y);
    }
    sort(v.begin(),v.end());
}

// define the colour between x & y
char define(int x,int y) {
    for(int i=n;i>=0;i--) {
        if(x >= a[i].x && y <= a[i].y) return a[i].c;
    }
}
/// define all the colours
void solve() {
    for(int i=0;i<v.size()-1;i++) {
        line[i].x = v[i];
        line[i].y = v[i+1];
        line[i].c = define(v[i],v[i+1]);
    }
}

// find the longest 'w' sequence and write bstart & bend to the output
void out() {
    int bstart = 0 ,
        start = 0 ,
        bend = 0 ,
        end = 0 ,
        all = 0 ,
        ball = 0;
    unsigned int i;
    for(i=0;i<v.size();i++) {
        start = line[i].x;
        all = 0;
        while(line[i].c=='w') {
            end = line[i].y;
            all+=(line[i].y - line[i].x);
            if(all>ball) {
                ball = all;
                bstart = start;
                bend = end;
            }
            i++;
        }
    }
    cout<<bstart<<" "<<bend<<endl;
}

int main() {
    init();
    solve();
    out();
    return 0;
}