Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <cmath>
- #include <fstream>
- using namespace std;
- struct node{
- int value;
- int set_val;
- };
- vector<node> build ( int wall_l, int& x){
- x = 1;
- while (x <= wall_l)
- x <<= 1;
- vector<node> tree(2*x);
- for(int i = 0; i < 2*x; i++) {
- tree[i].value = 0;
- tree[i].set_val = 100000000 + 1;
- }
- for(int i = 0; i < wall_l; i++)
- tree[x + i - 1].value = 0;
- for(int i = x - 2; i >= 0; i--)
- tree[i].value = min(tree[2*i + 1].value,tree[2*i +2].value);
- return tree;
- }
- void push (int v , int tl, int tr, vector<node>& tree){
- if(tree[v].set_val != 100000000 + 1 ){
- tree[v].value = tree[v].set_val;
- if( tl != tr){
- tree[2*v + 1].set_val = tree[v].set_val;
- tree[2*v + 2].set_val = tree[v].set_val;
- }
- tree[v].set_val = 100000000 + 1;
- }
- }
- void ragemod(int v, int tl, int tr, int l, int r,
- int set,vector<node>& tree){
- push(v,tl,tr,tree);
- if(l > tr || r < tl ){
- return;
- }
- if(l <= tl && tr <= r){
- //if(set != 100000000 + 1){
- tree[v].set_val = set;
- //}
- push(v,tl,tr,tree);
- return;
- }
- int tm = (tr + tl)/2;
- ragemod(2*v + 1,tl,tm,l,r,set,tree);
- ragemod(2*v + 2,tm + 1,tr,l,r,set,tree);
- tree[v].value = min(tree[2*v + 1].value,tree[2*v + 2].value);
- }
- vector< int> get_min( int v, int l, int r, int a, int b,vector<node>& tree){
- push(v,l,r,tree);
- if (r < a || b < l){
- vector< int> res;
- res.push_back(100000000 + 1);
- res.push_back(v);
- res.push_back(l);
- res.push_back(r);
- return res;
- }
- if (l >= a && r <= b){
- vector< int> res;
- res.push_back(tree[v].value);
- res.push_back(v);
- res.push_back(l);
- res.push_back(r);
- return res;
- }
- int m = (l + r) / 2;
- vector< int> res;
- vector< int> res1 = get_min( 2 * v + 1, l, m, a, b,tree);
- vector< int> res2 = get_min(2 * v + 2, m + 1, r, a, b,tree);
- if(res1[0] <= res2[0]){
- res.push_back(res1[0]);
- res.push_back(res1[1]);
- res.push_back(res1[2]);
- res.push_back(res1[3]);
- }
- else if (res1[0] > res2[0]){
- res.push_back(res2[0]);
- res.push_back(res2[1]);
- res.push_back(res2[2]);
- res.push_back(res2[3]);
- }
- return res;
- }
- int search_index(int v, int tl, int tr, vector<node>& tree,int x ){
- if( v < x - 1) {
- int tm = (tl + tr) / 2;
- push(2 * v + 1, tl, tm, tree);
- push(2 * v + 2, tm + 1,tr,tree);
- if (tree[2 * v + 1].value == tree[v].value) {
- return search_index( 2 * v + 1, tl, tm, tree,x);
- }
- else if (tree[2 * v + 2].value == tree[v].value) {
- return search_index( 2 * v + 2, tm + 1, tr, tree,x);
- }
- }
- else {
- return v;
- }
- }
- int main() {
- ifstream in("chinatown.in");
- int length_wall, op_count;
- cin >> length_wall >> op_count;
- int x = 1;
- vector<node> tree = build(length_wall,x);
- cout << endl;
- for (int i = 0; i < op_count ; i++){
- string op_type;
- cin >> op_type;
- if(op_type == "defend"){
- int a, b, c;
- cin >> a >> b >> c;
- ragemod(0,0,x - 1,a - 1,b - 1,c,tree);
- }
- else if (op_type == "attack"){
- int a, b;
- cin >> a >> b;
- vector< int> result = get_min(0,0,x - 1,a - 1,b - 1,tree);
- cout << result[0] << " " << search_index(result[1],result[2],result[3],tree,x) - x + 2<<endl;
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement