fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define FOR(i, a, b) for (int i = a; i <= b; ++i)
  3. using namespace std;
  4.  
  5. const int N = 150005;
  6.  
  7. int sub, t, n, m, q;
  8. vector<pair<int,int>> person[N]; 
  9. vector<int> poisen[N];           
  10. int last[N];                      
  11. vector<int> gay;                 
  12. vector<vector<int>> S;          
  13.  
  14. bool cmp(const vector<int> &a, const vector<int> &b) {
  15.     return a.size() < b.size();
  16. }
  17.  
  18. void solve() {
  19.     cin >> n >> m >> q;
  20.     FOR(i,1,n) { person[i].clear(); last[i]=0; }
  21.     FOR(i,1,m) poisen[i].clear();
  22.     gay.clear(); S.clear();
  23.  
  24.     FOR(i,1,q) {
  25.         char type; int p, d, t;
  26.         cin >> type >> p;
  27.         if(type=='+') {
  28.             cin >> d >> t;
  29.             person[p].push_back({d,t});
  30.             poisen[d].push_back(p);
  31.         } else {
  32.             cin >> t;
  33.             last[p] = t;
  34.         }
  35.     }
  36.  
  37.     FOR(i,1,m) {
  38.         sort(poisen[i].begin(), poisen[i].end());
  39.         poisen[i].erase(unique(poisen[i].begin(), poisen[i].end()), poisen[i].end());
  40.     }
  41.  
  42.     FOR(i,1,n) if(last[i]) gay.push_back(i);
  43.  
  44.     if(gay.empty()) {
  45.         int ans=0;
  46.         FOR(i,1,m) ans = max(ans, (int)poisen[i].size());
  47.         cout << ans << ' ';
  48.         return;
  49.     }
  50.  
  51.     bool ok = true;
  52.     for(int x : gay) {
  53.         vector<int> tmp;
  54.         for(auto [d,t] : person[x]) if(t < last[x]) tmp.push_back(d);
  55.         if(tmp.empty()) ok = false;
  56.         sort(tmp.begin(), tmp.end());
  57.         tmp.erase(unique(tmp.begin(), tmp.end()), tmp.end());
  58.         S.push_back(tmp);
  59.     }
  60.  
  61.     if(!ok) {
  62.         cout << "-1 ";
  63.         return;
  64.     }
  65.  
  66.     sort(S.begin(), S.end(), cmp);
  67.  
  68.     set<int> cand;
  69.     for(int x : S[0]) cand.insert(x);
  70.     for(int i=1;i<S.size();i++){
  71.         set<int> nxt;
  72.         for(int x : S[i]) if(cand.count(x)) nxt.insert(x);
  73.         swap(nxt,cand);
  74.         if(cand.empty()) {
  75.             cout << "-1 ";
  76.             return;
  77.         }
  78.     }
  79.  
  80.     int ans = 0;
  81.     for(int x : cand) ans = max(ans, (int)poisen[x].size());
  82.     cout << ans << ' ';
  83. }
  84.  
  85. int main() {
  86.     ios_base::sync_with_stdio(0);
  87.     cin.tie(0); cout.tie(0);
  88.  
  89.     if(fopen("diduduadi.inp","r")){
  90.         freopen("diduduadi.inp","r",stdin);
  91.         freopen("diduduadi.out","w",stdout);
  92.     }
  93.  
  94.     cin >> sub >> t;
  95.     while(t--) solve();
  96.  
  97.     return 0;
  98. }
Success #stdin #stdout 0.01s 10624KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/jgBriz
language:
C++14 (clang 8.0)
created:
6 hours 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!