oj.uz

Submission #283705

# Submission time Handle Problem Language Result Execution time Memory
283705 2020-08-26T05:53:11 Z 문홍윤(#5764) Ruka (COI15_ruka) C++17
100 / 100
 286 ms 16356 KB 
#include <bits/stdc++.h>
#define eb emplace_back
#define mp make_pair
#define F first
#define S second
#define svec(x) sort(x.begin(), x.end())
#define press(x) x.erase(unique(x.begin(), x.end()), x.end())
using namespace std;
typedef pair<int, int> pii;
const int inf=1e9;

const int MAXX=6e8;

struct SEGMENT_TREE{
    struct NODE{
        NODE *l, *r;
        int sum;
        NODE(){sum=0; l=r=0;}
    }*rt;
    SEGMENT_TREE(){rt=new NODE();}
    int query(NODE *nd, int s, int e, int a, int b){
        if(e<a||s>b)return 0;
        if(a<=s&&e<=b)return nd->sum;
        int ret=0;
        if(nd->l)ret+=query(nd->l, s, (s+e)/2, a, b);
        if(nd->r)ret+=query(nd->r, (s+e)/2+1, e, a, b);
        return ret;
    }
    int query(int a, int b){return query(rt, 0, 2*MAXX, a+MAXX, b+MAXX);}
    void update(NODE *nd, int s, int e, int num, int val){
        nd->sum+=val;
        if(s==e)return;
        if(num<=(s+e)/2){
            if(!nd->l)nd->l=new NODE();
            update(nd->l, s, (s+e)/2, num, val);
        }
        else{
            if(!nd->r)nd->r=new NODE();
            update(nd->r, (s+e)/2+1, e, num, val);
        }
    }
    void update(int num, int val){update(rt, 0, 2*MAXX, num+MAXX, val);}
};

int n, q;

struct VECTOR_CONT{
    SEGMENT_TREE mn, mx;
    int pnt[100010], arr[100010], d, cur, ans;
    void init(vector<int> vc){
        d=ans=0, cur=1;
        arr[0]=1;
        for(int i=1; i<=n; i++)arr[i]=arr[i-1]+vc[i-1];
        for(int i=1; i<=n; i++)pnt[i]=vc[i-1];
        for(int i=1; i<n; i++){
            mn.update(min(arr[i], arr[i+1]), 1);
            mx.update(max(arr[i], arr[i+1]), 1);
        }
    }
    int query(){
        int ret=ans+mn.query(-MAXX, -d-1)-mx.query(-MAXX, -d);
        if(arr[cur-1]<0&&arr[cur]+d>0)ret++;
        if(arr[cur-1]>0&&arr[cur]+d<0)ret++;
        return ret;
    }
    void update(int num){
        d+=num-pnt[cur];
        pnt[cur]=num;
    }
    void mv_lft(){
        if(cur==1)return;
        mn.update(min(arr[cur-1]-d, arr[cur]), 1);
        mx.update(max(arr[cur-1]-d, arr[cur]), 1);
        cur--;
        arr[cur]-=d;
        if(arr[cur-1]<0&&arr[cur]+d>0)ans--;
        if(arr[cur-1]>0&&arr[cur]+d<0)ans--;
    }
    void mv_rgt(){
        if(cur==n)return;
        if(arr[cur-1]<0&&arr[cur]+d>0)ans++;
        if(arr[cur-1]>0&&arr[cur]+d<0)ans++;
        cur++;
        mn.update(min(arr[cur-1], arr[cur]), -1);
        mx.update(max(arr[cur-1], arr[cur]), -1);
        arr[cur-1]+=d;
    }
}x, y;

int main(){
    scanf("%d", &n);
    vector<int> xx, yy;
    for(int i=1; i<=n; i++){
        int a, b;
        scanf("%d %d", &a, &b);
        xx.eb(a); yy.eb(b);
    }
    x.init(xx);
    y.init(yy);
    scanf("%d", &q);
    for(int i=1; i<=q; i++){
        char c;
        scanf(" %c", &c);
        if(c=='Q')printf("%d\n", x.query()+y.query());
        if(c=='C'){
            int a, b;
            scanf("%d %d", &a, &b);
            x.update(a);
            y.update(b);
        }
        if(c=='F'){
            x.mv_rgt();
            y.mv_rgt();
        }
        if(c=='B'){
            x.mv_lft();
            y.mv_lft();
        }
    }
}

/*
6
2 2
2 -6
-2 -4
-6 4
10 -10
-8 12
16
Q
C -4 -4
F
F
Q
F
C 6 -2
B
B
B
Q
C 0 6
Q
F
C -8 4
Q
*/


/*
5
6 2
0 -6
-2 2
-6 -8
4 0
12
Q
C 4 4
Q
F
F
F
C -6 -2
Q
B
B
C -4 -6
Q
*/

Compilation message

ruka.cpp: In function 'int main()':
ruka.cpp:91:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   91 |     scanf("%d", &n);
      |     ~~~~~^~~~~~~~~~
ruka.cpp:95:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   95 |         scanf("%d %d", &a, &b);
      |         ~~~~~^~~~~~~~~~~~~~~~~
ruka.cpp:100:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  100 |     scanf("%d", &q);
      |     ~~~~~^~~~~~~~~~
ruka.cpp:103:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  103 |         scanf(" %c", &c);
      |         ~~~~~^~~~~~~~~~~
ruka.cpp:107:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  107 |             scanf("%d %d", &a, &b);
      |             ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 512 KB Output is correct
2 Correct 2 ms 512 KB Output is correct
3 Correct 2 ms 512 KB Output is correct
4 Correct 2 ms 512 KB Output is correct

Subtask #2
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 512 KB Output is correct
2 Correct 2 ms 512 KB Output is correct
3 Correct 2 ms 512 KB Output is correct
4 Correct 2 ms 512 KB Output is correct
5 Correct 84 ms 4724 KB Output is correct
6 Correct 77 ms 5368 KB Output is correct
7 Correct 87 ms 3060 KB Output is correct
8 Correct 75 ms 3124 KB Output is correct

Subtask #3
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 512 KB Output is correct
2 Correct 2 ms 512 KB Output is correct
3 Correct 2 ms 512 KB Output is correct
4 Correct 2 ms 512 KB Output is correct
5 Correct 84 ms 4724 KB Output is correct
6 Correct 77 ms 5368 KB Output is correct
7 Correct 87 ms 3060 KB Output is correct
8 Correct 75 ms 3124 KB Output is correct
9 Correct 232 ms 14624 KB Output is correct
10 Correct 275 ms 16356 KB Output is correct
11 Correct 243 ms 10588 KB Output is correct
12 Correct 286 ms 13412 KB Output is correct