რაინდთა ტურნირი



 

დროის შეზღუდვა: 3 წამი

მეხსიერების შეზღუდვა: 256 მეგაბაიტი

             ბერლანდიის მეფემ, ბერლ მეორემ გადაწყვიტა, რომ რაინდის ტურნირი ჩაატაროს. მეფემ უკვე გაუგზავნა წერილი სამეფოს ყველა რაინდს და მათ ამ დიდებულ ტურნირზე მონაწილეობის მიღებაზე თანხმობა განაცხადეს.

             შენ ხარ უბრალო გლეხი. გასაკვირი არაა, რომ დილით ჩაგეძინა და ტურნირზე მისვლა დააგვიანე (თანაც უიქენდია). შენ კი ახლა ძალიან გაინტერესებს შეჯიბრის შედეგები. ბერლანდიაში ტურნირი შემდეგი წესების მიხედვით ტარდება:

·         ტურნირზე მონაწილეობას იღებს n რაინდი. თითოეულ რაინდს აქვს უნიკალური ნომერი 1-დან n-ის ჩათვლით.

·         ტურნირი შედგება m ბრძოლისგან. i-იურ რაუნდში რაინდები, რომლებიც ჯერ კიდევ თამაშში იყვნენ ნომრებით მინიმუმ li და მაქსიმუმ ri იბრძოლებენ იმისათვის, რომ ტურნირზე მონაწილეობა გააგრძელონ.

·         i-იური რაუნდის შემდეგ ყველა მონაწილეს შორის გამარჯვებული არის მხოლოდ ერთი (რაინდი ნომრით xi), ის განაგრძობს შეჯიბრზე მონაწილეობას, დანარჩენები კი ეთიშებიან გათამაშებას.

·         ბოლო, მე-m-ე რაუნდის გამარჯვებული (რაინდი ნომრით xm) ხდება მთლიანად ტურნირის გამარჯვებული.

             შენი მეგობრებისგან უკვე შენ შეაგროვე ყველა ინფორმაცია ბრძოლების შესახებ. ახლა კი თითოეული რაინდისთვის გჭირდება მისი სახელი, ვინაც იგი დაამარცხა. ჩვენ ვფიქრობთ, რომ რაინდი ნომერი b დაამარცხა რაინდმა ნომრით a, თუ ამ მომენტამდე ამ რაინდებს შორის იყო ბრძოლა და გამარჯვებული გამოვიდა a.

             დაწერეთ პროგრამა, რომელიც თითოეული რაინდისთვის გამოითვლის იმ რაინდს, რომელმაც ის დაამარცხა.

შესატანი მონაცემები

             პირველი ხაზი შეიცავს 2 მთელ რიცხვს - n, m (2 ≤ n ≤ 3·105; 1 ≤ m ≤ 3·105) - რაინდების რაოდენობა და ბრძოლების რაოდენობა. მომდევნო m ხაზი შეიცავს 3 მთელ რიცხვს - li,ri,xi (1li<rin; lixiri) – i-იური ბრძოლის აღწერა.

გარანტირებულია, რომ შესატანი მონაცემები სწორია და თითოეულ ბრძოლაში მინიმუმ 2 რაინდი იღებს მონაწილეობას.

გამოსატანი მონაცემები

             დაბეჭდეთ n მთელი რიცხვი. თუ i-იურმა რაინდმა წააგო, მაშინ i-იური ნომერი უნდა იყოს იმ რაინდის ნომერი, რომელმაც იგი დაამარცხა. თუ i-იური რაინდი არის გამარჯვებული და არავის დაუმარცხებია, მაშინ i-იურ ადგილზე უნდა დაბეჭდოთ 0.

მაგალითები

შემომავალი მონაცემები

გამავალი მონაცემები

4 3

1 2 1

1 3 3

1 4 4

3 1 4 0

შემომავალი მონაცემები

გამავალი მონაცემები

8 4

3 5 4

3 7 6

2 8 8

1 8 1

0 8 4 6 4 8 6 1

შენიშვნა

განვიხილოთ პირველი მაგალითი. რაინდებმა ნომრებით 1 და 2, იბრძოლეს, გამარჯვებული გამოვიდა პირველი რაინდი. მეორე ბრძოლაში პირველმა და მესამე რაინდებმა იბრძოლეს, მოიგო მესამემ. ბოლო ბრძოლა მესამე და მეოთხე რაინდებს შორის შედგა, რომელიც მეოთხემ მოიგო.


პირველ რიგში, მონაცემთა რომელიმე მარტივ სტრუქტურაში, მაგალითად სეტში, შევინახოთ ყველა რაინდის ნომერი, რომლითაც ისინი ტურნირზე ასპარეზობენ ანუ 1-დან n-ის ჩათვლით.

          გარდა ამისა დაგვჭირდება კიდევ ერთი მარტივი მონაცემთა სტრუქტურა, რომელშიც შევინახავთ შედეგებს, ანუ რომელი რაინდი ვისთან დამარცხდა. მაგალითად გამოგვადგება მთელი რიცხვების ვექტორი ან უბრალოდ მასივი.

          მომხმარებელს შემოჰყავს 3 მთელი რიცხვი (L, R და X) ანუ ეს იმას ნიშნავს, რომ X ნომრის მქონე რაინდმა, L-დან R-ის ჩათვლით ყველა ნომრის მქონე რაინდი დაამარცხა (რა თქმა უნდა X-ის ჩაუთვლელად).

          როდესაც მომხმარებელი ამ 3 მთელ რიცხვს შემოიყვანს, ყოველ ჯერზე გავაკეთოთ შემდეგი რამ: ავიღოთ სეტის იტერატორის ცვლადი, რომელშიც შევინახავთ ქვედა ზღვარს ანუ L-ს.

          სანამ დერეფერენსირებული იტერატორის ცვლადი ნაკლები იქნება ზედა ზღვარზე ანუ R-ზე მანამ ვაკეთებთ შემდეგ რამეს: თუ იტერატორი (დერეფერენსირებული) უტოლდება X-ს ანუ გამარჯვებულ რაინდს, მაშინ იტერატორს ვზრდით ერთით, წინააღმდეგ შეთხვევაში იმ ვექტორში, სადაც შედეგებს ვინახავთ, იტერატორს-1 ინდექსზე შევინახავთ გამარჯვებული რაინდის ნომერს ანუ X-ს და სეტიდან წავშლით იტერატორს + 1-ს.

          ბოლოს კი ციკლის საშუალებით გადავუვლით ვექტორს, რომელშიც შედეგები გვაქვს შენახული და დავაბეჭდინებთ.

ფსევდო კოდი:

შეგვყავს N (რაინდების რაოდენობა) და M (ბრძოლების რაოდენობა);

შევქმნათ N ზომის ვექტორი ან მასივი;

ციკლის დახმარებით სეტში ვამატებთ რიცხვებს 1-დან N-ის ჩათვლით ანუ რაინდების ნომრებს;

ციკლით M რაოდენობაჯერ შემოგვყავს 3 მთელი რიცხვი (L, R, X){

          იტერატორი = ქვედა ზღვარს(L);

          სანამ იტერატორი ნაკლებია ზედა ზღვარზე(R){

                        თუ იტერატორი = გამარჯვებული რაინდის ნომერი(X){

                                    იტერატორს++;

                        } წინააღმდეგ შემთხვევაში{

                                    ვეტქორი[იტერატორს-1] = X;

                                    სეტიდან წავშლით იტერატორს+1;

                        }

          }

}

ციკლით დავაბეჭდინოთ ვექტორის თითოეულ ინდექსზე მყოფი მთელი რიცხვი;

#include <iostream>
#include <vector>
#include <set>
using namespace std;

int main(){
    int n, m;
    cin >> n >> m;

    vector<int> vec(n);
    set<int> s;
    set<int>::iterator it;

    for(int i=0; i<=n; i++) s.insert(i+1);

    for(int i=0; i<m; i++){
        int l, r, x;
        cin >> l >> r >> x;
        
        it = s.lower_bound(l);
        while(*it <= r){
            if(*it == x){
                it++;
            } else{
                vec[*it - 1] = x;
                s.erase(it++);
            }
        }
    }

    for(int i=0; i<vec.size(); i++){
        cout << vec[i] << endl;
    }
    
    return 0;
}