fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define int long long
  3.  
  4. #define fi first
  5. #define se second
  6. #define endl '\n'
  7. #define lb long double
  8.  
  9. #define vi std::vector<int>
  10. #define isz(v) (int) v.size()
  11. #define pii std::pair<int, int>
  12. #define all(v) v.begin(), v.end()
  13. #define vii vector<pair<int, int>>
  14.  
  15. #define loop cerr << "here" << endl;
  16. #define TIME 1.0 * clock() / CLOCKS_PER_SEC
  17.  
  18. using namespace std;
  19. typedef long long ll;
  20.  
  21. const int MAXN = 1e6 + 7;
  22. const int inf32 = 1e15;
  23.  
  24. template <typename T> void maximize(T &a, T b){if(a < b) a = b;}
  25. template <typename T> void minimize(T &a, T b){if(a > b) a = b;}
  26.  
  27. int pre[MAXN], nxt[MAXN], n, t;
  28. string s;
  29. vii seg[MAXN];
  30.  
  31.  
  32. signed main(){
  33.     ios::sync_with_stdio(false);
  34.     cin.tie(nullptr);
  35.     #define task "t"
  36.     if (fopen(task".inp", "r")){
  37.         freopen(task".inp", "r", stdin);
  38.         freopen(task".out", "w", stdout);
  39.     }
  40.  
  41.     cin >> t;
  42.  
  43.  
  44.     while(t--){
  45.         for(int i = 1; i <= 2 * n; i++){
  46.             pre[i] = nxt[i] = 0;
  47.             seg[i].clear();
  48.         }
  49.         cin >> n >> s;
  50.         s = ' ' + s;
  51.         int openCnt = 0;
  52.  
  53.         for(int i = 1; i <= n; i++){
  54.             int L, R;
  55.             cin >> L >> R;
  56.  
  57.             if(s[L] == '(' and s[L] == s[R]){
  58.                 openCnt++;
  59.                 pre[L]++;
  60.             }
  61.  
  62.             if(s[L] == ')' and s[R] == s[L]){
  63.                 pre[R]--;
  64.             }
  65.  
  66.             if(s[L] == '(' and s[R] == ')'){
  67.                 pre[R]--;
  68.                 seg[L].push_back({L, R});
  69.             }
  70.  
  71.             if(s[L] == ')' and s[R] == '('){
  72.                 pre[L]--;
  73.                 seg[L].push_back({L, R});
  74.             }
  75.  
  76.         }
  77.         if(n & 1){
  78.             cout << "No" << endl;
  79.             continue;
  80.         }
  81.  
  82.         int cnt = 0;
  83.         priority_queue<pii, vii, greater<pii>> pq;
  84.         bool check = 1;
  85.  
  86.         for(int i = 1; i <= 2 * n; i++){
  87.             cnt += pre[i] + nxt[i];
  88.             for(auto x : seg[i]){pq.push({x.se, x.fi});} //ưu tiên R trái nhất trc
  89.  
  90.             if(cnt < 0){
  91.                 while(cnt < 0 and isz(pq)){
  92.                     int L = pq.top().se, R = pq.top().fi;
  93.                     pq.pop();
  94.                     if(L <= i) cnt++;
  95.                     else nxt[L]++;
  96.                     if(R <= i) cnt++;
  97.                     else nxt[R]++;
  98.                 }
  99.             }
  100.             if(cnt < 0){
  101.                 check = 0;
  102.                 break;
  103.             }
  104.         }
  105.  
  106.         if(!check){
  107.             cout << "No" << endl;
  108.             continue;
  109.         }
  110.  
  111.         cout << (!cnt and check ? "Yes" : "No") << endl;
  112.     }
  113.  
  114. }
  115.  
Success #stdin #stdout 0.01s 28624KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/9Mmi01
language:
C++14 (gcc 8.3)
created:
1 day ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!