結果

問題 No.1673 Lamps on a line
コンテスト
ユーザー Yourein
提出日時 2022-02-04 17:00:39
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 160 ms / 2,000 ms
コード長 8,268 bytes
コンパイル時間 1,578 ms
コンパイル使用メモリ 121,276 KB
最終ジャッジ日時 2025-01-27 18:34:57
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 11
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <iomanip>
#include <cmath>
#include <algorithm>
#include <string>
#include <vector>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <queue>

#include <list>

//Binary Indexed Tree
// #include<ext/pb_ds/assoc_container.hpp>
// #include<ext/pb_ds/tree_policy.hpp>
// #include<ext/pb_ds/tag_and_trait.hpp>
// using namespace __gnu_pbds;
//Binary Indexed Tree

using namespace std;
using ll = long long;
using ld = long double;

#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()

//Vector in
template <typename T> istream &operator>>(istream &is, vector<T> &x){
    for (auto &y:x) is >> y; 
    return is;
}
//Vector in

//Vector out
template <typename T> ostream &operator<<(ostream &os, vector<T> &x){
    for (long long e = 0; e < (int)x.size(); e++){
        if (e == (int)x.size()-1) os << x[e];
        else os << x[e] << " ";
    }
    return os;
}
//Vector out

namespace cpio{
    //IO library for Competitive-Programming
    struct scanner {
        private:
            struct reader {
                template <typename T> operator T() const {T buf; std::cin >> buf; return buf;}
            };
        public:
            scanner() {std::cin.sync_with_stdio(false); std::cin.tie(nullptr);}

            reader operator()() const {return reader();}
    };

    //Debug out
    void dout(){
        cerr << "\n";
    }
    template<typename T, typename... Ts>
    void dout(const T& a, const Ts&... b){
        cerr << a;
        (cerr << ... << (cerr << ' ', b));
        cerr << "\n";
    }

    template<typename... T>
    void input(T&... a){
        (cin >> ... >> a);
    }
}

namespace cpmath{
    //Math library for Competitive-Programming
    const ll mod97 = 1000000007;
    const ll mod99 = 1000000009;
    const ll mod89 = 998244353;
    const long double pi = 3.14159265359;
    std::unordered_set<long long> allowed_mod;
    std::unordered_set<long long> unallowed_mod;

    constexpr int DX4[4] = {1, 0, -1, 0};
    constexpr int DY4[4] = {0, 1, 0, -1};
    constexpr int DX8[8] = {-1, 0, 1, -1, 1, -1, 0, 1};
    constexpr int DY8[8] = {-1, -1, -1, 0, 0, 1, 1, 1};

    ll factorial(ll a, ll b = -1, const ll fmod = -1){
        ll ans = 1;
        if (fmod > 1) {
            if (b == -1) for (ll i = a; i > 1; i--) ans = ((ans%fmod)*(i%fmod))%fmod;
            else for (ll i = a; i >= b; i--) ans = ((ans%fmod)*(i%fmod))%fmod;
        }
        else{
            if (b == -1) for (ll i = a; i > 1; i--) ans = ans*i;
            else for(ll i = a; i >= b; i--) ans = ans*i;
        }
        return ans;
    }

    ll fastpow(ll m, ll p){
        if (p == 0) return 1;
        if (p%2 == 0){
            ll t = fastpow(m, p/2);
            return t*t;
        }
        return m*fastpow(m, p-1);
    }

    ll modpow(ll m, ll p, const ll fmod){
        if (p == 0) return 1;
        if (p%2 == 0){
            ll t = modpow(m, p/2, fmod);
            return (t*t)%fmod;
        }
        return (m*modpow(m, p-1, fmod))%fmod;
    }

    ld dtor(const ld deg){return deg*(pi/(ld)180);}

    string basen(ll raw, int to){
        char c[] = {'0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 'A', 'B', 'C', 'D', 'E', 'F'};
        string res = "";

        while(raw){
            res.push_back(c[raw%to]);
            raw/=to;            
        }

        reverse(res.begin(), res.end());
        return res;
    }

    template <typename T = long long>
    class modint{
    private:
        T num;
        long long mod;
        bool set_prime_flag;
    public:
        explicit modint(T n, long long m = cpmath::mod99, bool pflag = true){
            num = static_cast<T>(n);
            set_prime_flag = pflag;
            
            if (pflag == true){
                if (mod_is_prime(m)) mod = m;
                else throw std::invalid_argument("Invalid value for mod: Check mod is prime number or set plag to false");
            }
            else mod = m;
        } //modint constructer

        //+ operator
        constexpr modint operator+(modint &t){return modint((this->raw()+t.raw())%this->mod, this->mod, this->set_prime_flag);}
        constexpr modint operator+(long long t){return modint((this->raw()+t)%this->mod, this->mod, this->set_prime_flag);}
        constexpr modint operator+=(modint &t){
            this->num = (this->raw()+t.raw())%mod;
            return modint(this->num, mod, set_prime_flag);
        }
        constexpr modint operator+=(long long t){
            this->num = (this->raw()+t)%mod;
            return modint(this->num, mod, set_prime_flag);
        }
        //+ operator
        //- operator
        constexpr modint operator-(modint &t){return modint(((this->raw()-t.raw())%this->mod+this->mod)%this->mod, this->mod, this->set_prime_flag);}
        constexpr modint operator-(long long t){return modint(((this->raw()-t)%this->mod+this->mod)%this->mod, this->mod, this->set_prime_flag);}
        constexpr modint operator-=(modint &t){
            this->num = ((this->raw()-t.raw())%this->mod+this->mod)%this->mod;
            return modint(this->num, this->mod, this->set_prime_flag);
        }
        constexpr modint operator-=(long long t){
            this->num = ((this->raw()+t)%this->mod+this->mod)%this->mod;
            return modint(this->num, mod, this->set_prime_flag);
        }
        //- operator
        //* operator
        constexpr modint operator*(modint &t){return modint((this->raw()*t.raw())%this->mod, this->mod, this->set_prime_flag);}
        constexpr modint operator*(long long t){return modint((this->raw()*(t%mod))%this->mod, this->mod, this->set_prime_flag);}
        constexpr modint operator*= (modint &t){
            this->num = (this->raw()*t.raw())%this->mod;
            return modint(this->num, this->mod, this->set_prime_flag);
        }
        constexpr modint operator*=(long long t){
            this->num = (this->raw()*(t%mod))%mod;
            return modint(this->num, this->mod, this->set_prime_flag);
        }
        //* operator

        //= operator
        constexpr modint operator=(long long t){
            this->num = t%mod;
            return modint(this->num, this->mod, this->set_prime_flag);
        }
        //= operator

        void plus(T n){num = (num+(n%mod))%mod;}
        void minus(T n){num = ((num-(n%mod))%mod+mod)%mod;}
        void multi(T n){num = ((num%mod)*(n%mod))%mod;}
        void div(T n){
            if (set_prime_flag == false) throw std::logic_error("Not Divisible in case you don't set pflag true");
            else num = (num*inversed(n))%mod;
        }
        
        T raw(){return num;}
    private:
        long long inversed(ll n){
            return cpmath::modpow(n, mod-2, mod);
        }

        bool mod_is_prime(int n){
            if (n == cpmath::mod97 || n == cpmath::mod99 || n == cpmath::mod89 || cpmath::allowed_mod.count(n) > 0){
                return true;
            }
            else if (cpmath::unallowed_mod.count(n) > 0){
                return false;
            }
            else{
                for (ll i = 2; i*i <= n; i++){
                    if (n%i == 0) {
                        cpmath::unallowed_mod.insert(n);
                        return false;
                    }
                }
                cpmath::allowed_mod.insert(n);
                return true;
            }
        } //mod_is_prime
    }; //modint
}

cpio::scanner in;
using cpio::dout;
using cpio::input;
using cpmath::mod89;
using cpmath::mod97;
using cpmath::mod99;
using cpmath::modint;
//using cpmath::DX4;
//using cpmath::DY4;
//using cpmath::DX8;
//using cpmath::DY8;

//GNU Binary Indexed Tree
// template<typename T>
// using gtree = tree<T, null_type, greater<T>, rb_tree_tag, tree_order_statistics_node_update>;

int main(){
    ll n, q;
    cin >> n >> q;

    vector<bool> lamps(n, false);

    ll ans = 0;

    for (int i = 0; i < q; i++){
        ll li, ri; cin >> li >> ri;
        li--;

        for (int j = li; j < ri; j++) {
            if (lamps[j] == true){
                lamps[j] = false;
                ans--;
            }
            else{
                lamps[j] = true;
                ans++;
            }
        }

        cout << ans << endl;
    }
}
0