SHARE
TWEET

Untitled

a guest Aug 20th, 2019 62 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. // OBI 2014 - 2nd Stage - Frequencia
  2. // Lúcio Cardoso
  3.  
  4. #include <bits/stdc++.h>
  5.  
  6. using namespace std;
  7.  
  8. const int maxn = 2e5+10;
  9. const int maxr = 55;
  10.  
  11. int bit[2][maxr][maxn];
  12.  
  13. int lastC[maxn], lastL[maxn];
  14. int timeC[maxn], timeL[maxn];
  15.  
  16. int qtd[maxr];
  17.  
  18. void upd(int x, int v, int k1, int k2)
  19. {
  20.     for (; x < maxn; x += (x&-x))
  21.         bit[k1][k2][x] += v;
  22. }
  23.  
  24. int soma(int x, int k1, int k2)
  25. {
  26.     int ans = 0;
  27.     for (; x > 0; x -= (x&-x))
  28.         ans += bit[k1][k2][x];
  29.     return ans;
  30. }
  31.  
  32. int main(void)
  33. {
  34.     int n, q;
  35.     scanf("%d %d", &n, &q);
  36.  
  37.     for (int i = 1; i <= n; i++)
  38.     {
  39.         timeL[i] = timeC[i] = i;
  40.         upd(i, 1, 0, 0);
  41.         upd(i, 1, 1, 0);
  42.     }
  43.  
  44.     for (int i = 1; i <= q; i++)
  45.     {
  46.         int op;
  47.         scanf("%d", &op);
  48.  
  49.         if (op == 1)
  50.         {
  51.             int x, r;
  52.             scanf("%d %d", &x, &r);
  53.  
  54.             upd(timeL[x], -1, 0, lastL[x]);
  55.  
  56.             timeL[x] = i+n+1, lastL[x] = r;
  57.             upd(timeL[x], 1, 0, lastL[x]);
  58.         }
  59.         else if (op == 2)
  60.         {
  61.             int x, r;
  62.             scanf("%d %d", &x, &r);
  63.  
  64.             upd(timeC[x], -1, 1, lastC[x]);
  65.  
  66.             timeC[x] = i+n+1, lastC[x] = r;
  67.             upd(timeC[x], 1, 1, lastC[x]);
  68.         }
  69.         else if (op == 3)
  70.         {
  71.             int x;
  72.             scanf("%d", &x);
  73.  
  74.             memset(qtd, 0, sizeof qtd);
  75.  
  76.             int tot = 0;
  77.             for (int i = 0; i <= 50; i++)
  78.             {
  79.                 qtd[i] += (soma(maxn-1, 1, i)-soma(timeL[x], 1, i));
  80.                 tot += qtd[i];
  81.             }
  82.  
  83.             qtd[lastL[x]] += n-tot;
  84.  
  85.             int mx = 0, ind = 0;
  86.             for (int i = 50; i >= 0; i--)
  87.                 if (qtd[i] > mx)
  88.                     mx = qtd[i], ind = i;
  89.  
  90.             printf("%d\n", ind);
  91.         }
  92.         else
  93.         {
  94.             int x;
  95.             scanf("%d", &x);
  96.  
  97.             memset(qtd, 0, sizeof qtd);
  98.  
  99.             int tot = 0;
  100.             for (int i = 0; i <= 50; i++)
  101.             {
  102.                 qtd[i] += (soma(maxn-1, 0, i)-soma(timeC[x], 0, i));
  103.                 tot += qtd[i];
  104.             }
  105.  
  106.             qtd[lastC[x]] += n-tot;
  107.  
  108.             int mx = 0, ind = 0;
  109.             for (int i = 50; i >= 0; i--)
  110.                 if (qtd[i] > mx)
  111.                     mx = qtd[i], ind = i;
  112.  
  113.             printf("%d\n", ind);
  114.         }
  115.     }
  116. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top