Submission #40015110

---

Source Code Expand

#include<bits/stdc++.h>
#include<atcoder/all>
using namespace std;
using namespace atcoder;
using ll=long long;
template<class T,class U> inline bool chmin(T&x,U y){if(x>y){x=y;return true;}return false;}
template<class T,class U> inline bool chmax(T&x,U y){if(x<y){x=y;return true;}return false;}
template <class T>
std::ostream &operator<<(std::ostream &out, const std::vector<std::vector<T>> &r){
    if(r.size() == 0){
        out << "||";
        return out;
    }
    for(const auto&v : r) out << v << endl;
    out << endl;
    return out;
}

template <class T>
std::ostream &operator<<(std::ostream &out, const std::vector<T> &r){
    if(r.size() == 0){
        out << "[]";
        return out;
    }
    out << "[";
    for(int i{}; i < (int)r.size() - 1; ++i) out << r[i] << ",";
    out << r.back() << "]";
    return out;
}

template <class T>
std::ostream &operator<<(std::ostream &out, const std::set<T> &r){
    if(r.size() == 0){
        out << "{}";
        return out;
    }
    out << "{";
    auto e = r.end(); --e;
    for(auto it = r.begin(); it != e; ++it) out << *it << ",";
    out << *e << "}";
    return out;
}

template <class T, class U>
std::ostream &operator<<(std::ostream &out, const std::map<T, U> &r){
    if(r.size() == 0){
        out << "{}";
        return out;
    }
    out << "{";
    auto e = r.end(); --e;
    for(auto it = r.begin(); it != e; ++it) out << it -> first << ":" << it -> second << ",";
    out << e -> first << ":" << e -> second << "}";
    return out;
}
 
template <class T, class U>
std::ostream &operator<<(std::ostream &out, const std::pair<T, U> &r){
    out << "(" << r.first << "," << r.second << ")";
    return out;
}

void solve(){
    int n;
    cin >> n;
    string s;
    cin >> s;
    using P = pair<int, int>;
    vector<P> st;
    vector<int> sm(4*n+1);
    for (int i = 0; i < 2*n; i++)
    {
        int l, r;
        cin >> l  >> r;
        --l, --r;
        if(s[l] == s[r])
        {
            if(s[l] == '(')
            {
                sm[l+1]++;
            }
            else{
                sm[r+1]--;
            }
        }
        else{
            if(s[l] == '(')
            {
                sm[l+1]++;
            }
            else
            {
                sm[r+1]++;
            }
            st.emplace_back(l, r);
        }
    }
    for (int i = 0; i < 4*n; i++)
    {
        sm[i+1] += sm[i];
    }
    
    //cerr << sm << endl;
    if(sm[4*n] < 0 or sm[4*n] % 2 == 1)
    {
        cout << "No" << '\n';
        return;
    }
    int x = sm[4*n] / 2;
    if(x > st.size())
    {
        cout << "No" << '\n';
        return;
    }
    for (int i = 0; i <= 2*n; i++)
    {
        sm[i] -= x;
    }
    for (int i = 2*n + 1; i <= 4*n; ++i)
    {
        sm[i] -= 2*x;
    }
    sort(begin(st), end(st), [](P l, P r){
        return l.second > r.second;
    });
    int id = 0;
    priority_queue<int> pq;
    int tmp = 0;
    vector<int> p(4*n + 1);
    for (int i = 4 * n; i >= 2*n + 1; --i)
    {
        while(id < st.size() and st[id].second == i)
        {
            pq.push(st[id].first);
            ++id;
        }
        while(sm[i] + tmp < 0)
        {
            if(pq.empty())
            {
                cout << "No" << '\n';
                return;
            }
            int L = pq.top();
            pq.pop();
            p[L]++;
            tmp++;
            --x;
            if(x < 0)
            {
                cout << "No" << '\n';
                return;
            }
        }
        sm[i] += tmp;
    }
    while(id < st.size())
    {
        pq.push(st[id].first);
        ++id;
    }
    while(x)
    {
        int L = pq.top();
        pq.pop();
        p[L]++;
        tmp++;
        --x;
    }
    for (int i = 2 * n; i >= 0; --i)
    {
        p[i] += p[i+1];
    }
    for (int i = 0; i <= 4*n; i++)
    {
        if(p[i] + sm[i] < 0)
        {
            cout << "No" << '\n';
            return;
        }
    }
    cout << "Yes" << '\n';
}

int main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    unsigned t;
    cin >> t;
    for(unsigned i{}; i < t; ++i){
        solve();
    }
}

Submission Info

Compile Error

./Main.cpp: In function ‘void solve()’:
./Main.cpp:110:10: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::vector<std::pair<int, int> >::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
  110 |     if(x > st.size())
      |        ~~^~~~~~~~~~~
./Main.cpp:132:18: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::vector<std::pair<int, int> >::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
  132 |         while(id < st.size() and st[id].second == i)
      |               ~~~^~~~~~~~~~~
./Main.cpp:157:14: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::vector<std::pair<int, int> >::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
  157 |     while(id < st.size())
      |           ~~~^~~~~~~~~~~

Judge Result