Spoj 7299. Multiples of 3 – Cpp solution

The idea is to build a segment tree and use lazy updates.
What is a lazy update? Say, that you have to update an interval [A;B]. It will be time consuming to update it if you are not going to query it later. So, when you find such an interval, don’t go further down the tree, but rather update what should be the value for this interval and memorize that the two children nodes have to be updated later. If you later go down that branch for either an update or for a query, just update (fix) the value for that node.
That’s all. For the segment tree, just keep all values of zeros, ones and twos. You do not need to keep what is the actual value, but rather the value mod 3.

#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;

struct Node {
    int zeros, ones, twos;
    Node() {
        zeros = ones = twos = 0;
    }
    Node(const Node & left, const Node & right) {
        zeros = left.zeros + right.zeros;
        ones = left.ones + right.ones;
        twos = left.twos + right.twos;
    }
};

Node tree[800016];
int lazy[800016];

void build(int idx, int sfrom, int sto) {
    if (sfrom == sto) {
        tree[idx].zeros = 1;
        return;
    }
    int left = idx<<1;
    int right = left+1;
    int mid = (sfrom + sto)>>1;
    build(left, sfrom, mid);
    build(right, mid+1, sto);
    tree[idx] = Node(tree[left], tree[right]);
}

void fix(int idx) {
    lazy[idx] %= 3;
    if (lazy[idx] == 1) {
        swap(tree[idx].zeros, tree[idx].twos);
        swap(tree[idx].ones, tree[idx].twos);
    } else if (lazy[idx] == 2) {
        swap(tree[idx].zeros, tree[idx].ones);
        swap(tree[idx].ones, tree[idx].twos);
    }
    lazy[idx<<1] += lazy[idx];
    lazy[(idx<<1)+1] += lazy[idx];
    lazy[idx] = 0;
}

void update(int idx, int sfrom, int sto, int qfrom, int qto) {
    if (sfrom == qfrom && sto == qto) {
        lazy[idx]+=1;
        fix(idx);
        return;
    }
    int left = idx<<1;
    int right = left+1;
    int mid = (sfrom+sto)>>1;
    if (lazy[idx]) fix(idx);
    if (qto <= mid) {
        update(left, sfrom, mid ,qfrom, qto);
    } else if (qfrom > mid) {
        update(right, mid+1, sto, qfrom, qto);
    } else {
        update(left, sfrom, mid, qfrom, mid);
        update(right, mid+1, sto, mid+1, qto);
    }
    fix(left);
    fix(right);
    tree[idx] = Node(tree[left], tree[right]);
}

int query(int idx, int sfrom, int sto, int qfrom, int qto) {
    if (sfrom == qfrom && sto == qto) {
        fix(idx);
        return tree[idx].zeros;
    }
    int left = idx<<1;
    int right = left+1;
    int mid = (sfrom+sto)>>1;
    if (lazy[idx]) fix(idx);
    if (qto <= mid) {
        return query(left, sfrom, mid, qfrom, qto);
    } else if (qfrom > mid) {
        return query(right, mid+1, sto, qfrom, qto);
    } else {
        return query(left, sfrom, mid, qfrom, mid)
            + query(right, mid+1, sto, mid+1, qto);
    }
}

int main() {
    cin.sync_with_stdio(0);
    int n,q;
    scanf("%d%d", &n, &q);
    build(1,1,n);
    int a,b,c;
    while (q--) {
        scanf("%d%d%d",&a,&b,&c);
        b+=1, c+=1;
        if (a == 0) {
            update(1,1,n,b,c);
        } else {
            printf("%dn", query(1,1,n,b,c));
        }
        //cout << "! " << lazy[1] << endl;
    }
    return 0;
}

6294. Yodaness Level C++ solution

The idea is to find the number of inverses which means
that given an array A. We have an inverse if
i < j, but A[i] > A[j]
In our case, we want to sort the words and we are interested in the minimum number of swaps using say insertion sort to accomplish this task.
We can use a segment tree.
We will two kinds of queries:
query(from, to) -> number of elements smaller than to
update(pos) -> number of elements smaller than pos incremented by 1

go over each element in the array and count the number of inverse of it. Say, that we are index I and we have added B elements which are smaller than A[I]. Then, we have I-B elements which are bigger => number of inverses is I-B. Then we also have to update the tree to node that we have added element A[I].
Code:

#include <iostream>
#include <string>
#include <cstring>
#include <unordered_map>
using namespace std;

typedef long long ll;

int n;
ll tree[200001];
int arr[30001];
unordered_map<string,size_t> mp;

ll query(int idx, int sfrom, int sto, int qfrom, int qto) {
    if (sfrom == qfrom && sto == qto) {
        return tree[idx];
    }
    int left = idx<<1;
    int right = left+1;
    int mid = (sfrom+sto)>>1;
    if ( qto <= mid) {
        return query(left, sfrom, mid, qfrom, qto);
    } else if (qfrom > mid) {
        return query(right, mid+1, sto, qfrom, qto);
    } else {
        return query(left, sfrom, mid, qfrom, mid)
            + query(right, mid+1, sto, mid+1,qto);
    }
}

void update(int idx, int sfrom, int sto, int pos) {
    if (sfrom == sto) {
        tree[idx]+=1;
        return;
    }
    int left = idx<<1;
    int right = left+1;
    int mid = (sfrom+sto)>>1;
    if ( pos <= mid) {
        update(left, sfrom, mid, pos);
    } else {
        update(right, mid+1, sto, pos);
    }
    tree[idx] = tree[left] + tree[right];
}

int main() {
    cin.sync_with_stdio(0);
    int t;
    cin >> t;
    while (t--) {
        cin >> n;
        string s;
        for (int i = 1;i<=n;++i) {
            cin >> s;
            mp.insert(make_pair(s, i));
        }
        for (int i = 1; i<=n;++i) {
            cin >> s;
            pair<string, size_t> found = *mp.find(s);
            arr[found.second] = i;
        }
        ll ans = 0;
        for (int i = 1; i<= n; ++i) {
            ans += (i - query(1,1,n,1,arr[i])-1);
            update(1,1,n,arr[i]);
        }
        cout << ans << endl;
        memset(tree,0,sizeof(tree));
        mp.clear();
    }
    return 0;
}

OpenGL Instanced rendering example

You can read about it at many places. Probably the red book and http://ogldev.atspace.co.uk/www/tutorial33/tutorial33.html are one of the best sources. However, there is a lot of information in the red book and the example which is given is not too clear. You just see something rendered and you may have not cover transformations yet or you do not know how to load some model from some file.
In Ogldev you have to read a lot of other tutorials to get aquainted what happens and the tutorial mostly modifies previously written code (the one about loading models with Assimp).
Also, it may be a bit hard to follow since a lot of other stuff is happening as well like texture mapping, etc.

#define GLM_FORCE_RADIANS
#include <glm/vec3.hpp>
#include <glm/vec4.hpp>
#include <glm/mat4x4.hpp>
#include <glm/gtc/matrix_transform.hpp>
#include <iostream>
#include <GL/glew.h>
#include <GL/freeglut.h>
#include <GL/glut.h>
#include <GL/gl.h>
#include "../common/Shader.hpp"
#include "../common/ShaderProgram.hpp"
using namespace glm;
using namespace std;

/*
    checks whether there are errors and prints them
*/
void checkForOpenglErrors() {
    GLenum glErr;
    while ((glErr = glGetError()) != GL_NO_ERROR) {
        std::cerr << "OpenGL error: " << glErr << std::endl;
    }
}

/*
    vertices of a pyramid
*/
GLfloat vertices[] = {
    -1,0,2,
    1,0,2,
    1,0,0,
    -1,0,0,
    0,1,1
};

/*
    indices to represent all of the faces (triangles) of the pyramid
*/
GLushort indices[] = {
    0,1,4,
    1,2,4,
    2,3,4,
    3,0,4
};

/*
    colors for each pyramid instance rendered
*/
GLfloat colors[] = {
    1,0,0,
    0,1,0,
    0,0,1
};

/* Vertex array */
GLuint VAO;

/* Buffers bind to vertex array */
#define NUM_BUFFERS 4
GLuint buffers[NUM_BUFFERS];


/* Locations of buffers in array */
#define POSITION_BUFFER 0
#define INDEX_BUFFER 1
#define COLOR_BUFFER 2
#define TRANS_BUFFER 3

/* Locations of attributes in vertex shader */
#define POSITION_ATTR_LOC 0
#define COLOR_ATTR_LOC 1
#define TRANS_ATTR_LOC 2

void init() {
    /* create aand use shader program */
    ShaderProgram program = ShaderProgram(Shader("shader.vert", GL_VERTEX_SHADER),
     Shader("shader.frag", GL_FRAGMENT_SHADER));
    glUseProgram(program.getProgram());

    /* generate the needed vertex array so that we can use later when rendering */
    glGenVertexArrays(1, &VAO);
    glBindVertexArray(VAO);

    /* generate buffers needed for the pyramid */
    glGenBuffers(NUM_BUFFERS, buffers);

    /* buffer to store vertices */
    glBindBuffer(GL_ARRAY_BUFFER, buffers[POSITION_BUFFER]);
    glBufferData(GL_ARRAY_BUFFER, sizeof(vertices), vertices, GL_STATIC_DRAW);
    glEnableVertexAttribArray(POSITION_ATTR_LOC);
    glVertexAttribPointer(POSITION_ATTR_LOC, 3, GL_FLOAT, GL_FALSE, 0, 0);

    /* index buffer */
    glBindBuffer(GL_ELEMENT_ARRAY_BUFFER, buffers[INDEX_BUFFER]);
    glBufferData(GL_ELEMENT_ARRAY_BUFFER, sizeof(indices), indices, GL_STATIC_DRAW);

    /* buffer for the colors of each pyramid */
    glBindBuffer(GL_ARRAY_BUFFER, buffers[COLOR_BUFFER]);
    glBufferData(GL_ARRAY_BUFFER, sizeof(colors), colors, GL_STATIC_DRAW);
    glVertexAttribPointer(COLOR_ATTR_LOC, 3, GL_FLOAT, GL_FALSE, 0, 0);
    // set change per instance -> every instance will have a new entry from the array buffer
    glVertexAttribDivisor(COLOR_ATTR_LOC, 1);
    glEnableVertexAttribArray(COLOR_ATTR_LOC);

    /*
        create just translate transformations for each pyramid -> 3 pyramids
    */
    mat4 transf[] = {
        translate(mat4(1.0f), vec3(-4.0f, -3.0f, -14.0f)),
        translate(mat4(1.0f), vec3(3.0f, -1.0f, -17.0f)),
        translate(mat4(1.0f), vec3(2.0f, -2.0f, -9.0f))
    };
    glBindBuffer(GL_ARRAY_BUFFER, buffers[TRANS_BUFFER]);
    glBufferData(GL_ARRAY_BUFFER, sizeof(transf), transf, GL_STATIC_DRAW);

    /*
        set the attrib location and enable it. since we have a 4x4 matrix we have
        4 columns of vectors of length 4.
    */
    for (int i = 0; i < 4; ++i) {
        glVertexAttribPointer(TRANS_ATTR_LOC+i, 4, GL_FLOAT, GL_FALSE, sizeof(mat4), (GLvoid *)(i*sizeof(vec4)));
        glVertexAttribDivisor(TRANS_ATTR_LOC+i, 1);
        glEnableVertexAttribArray(TRANS_ATTR_LOC+i);
    }

    // done with VAO
    // unbind
    glBindVertexArray(0);

    /*
        create projection transformation and update the uniform
    */
    GLint projectionLoc = glGetUniformLocation(program.getProgram(), "projection");
    mat4 projection = perspective(45.0f, 4.0f / 3.0f, 0.1f, 100.0f);
    glUniformMatrix4fv(projectionLoc, 1, GL_FALSE, &projection[0][0]);
}

void display() {
    checkForOpenglErrors();

    glClear(GL_COLOR_BUFFER_BIT);

    /* bind and draw */
    glBindVertexArray(VAO);

    /* sizeof(indices) / sizeof(GLushort) will return number of elements in the array */
    glDrawElementsInstanced(GL_TRIANGLES, sizeof(indices) / sizeof(GLushort), GL_UNSIGNED_SHORT, NULL, 3);

    glFlush();

}

int main(int argc, char ** argv)
{

    glutInit(&argc, argv);
    glutInitDisplayMode(GLUT_RGBA);
    glutInitWindowSize(512, 512);
    glutInitContextVersion(4,3); // freeglut required
    glutInitContextProfile(GLUT_CORE_PROFILE);
    glutCreateWindow("");
    glewExperimental=GL_TRUE;

    if (glewInit()) {
        cerr << "Problem initializing glew" << endl;
        exit(EXIT_FAILURE);
    }

    init();

    glutDisplayFunc(display);

    glutMainLoop();

    return 0;
}

Vertex shader:

#version 430 core

layout (location = 0) in vec3 position;

// per-instance attribute
layout (location = 1) in vec3 color;

// per-instance transformation
layout (location = 2) in mat4 trans;

uniform mat4 projection;


out vec4 col;

void main() {
    gl_Position = projection * trans * vec4(position, 1.0f);
    col = vec4(color, 1.0f);
}

Fragment shader

#version 430 core


in vec4 col;
out vec4 color;

void main() {
    color = col;
}

OpenGL Simple Fractal tree

I wanted to draw a simple 2d fractal tree. This is the result.
fractal

#include <iostream>
#include <string>
#include <GL/glew.h>
#include <GL/freeglut.h>
#include <GL/glut.h>
#include <GL/gl.h>

#include "../common/Shader.hpp"
#include "../common/ShaderProgram.hpp"

#include <vector>
#include <cmath>

using namespace std;

struct Vector {
    float x;
    float y;
    Vector(float _x, float _y) : x(_x), y(_y) {};
    Vector operator + (const Vector & rht) const {
        return Vector(x + rht.x, y + rht.y);
    };
    Vector operator * (float v) const {
        return Vector(x*v, y*v);
    };
};

struct Branch {
    Vector direction;
    Vector position;
    float length;
    Branch(float _x, float _y, float _posX, float _posY, float _length) :
        direction(Vector(_x, _y)), position(Vector(_posX, _posY)), length(_length) {};
    Branch(Vector _direction, Vector _position, float _length) :
        direction(_direction), position(_position), length(_length) {};
};

vector<Branch> branches;
vector<Vector> triangles;

float m_BranchingAngle;
float m_LengthFactor;
size_t m_MaxDepth;


/*
    Since branches have a starting position, length and direction, we will need the end position of the branch.
    This is the start of the next branch.
*/
Vector getEndOfBranch(const Branch & branch) {
    Vector pos = branch.position + branch.direction * branch.length;
    return pos;
}

/*
    Just transforms the angle from degrees to radians
*/
inline float toRad(float angle) {
    return angle * M_PI / 180.0f;
}

/*
    rotates a vector given an angle in degrees
    it just multiplies the vector by the matrix
    cos(x) -sin(x)
    sin(x) cos(x)
*/
Vector rotateVector(const Vector & vec, float angle) {
    angle = toRad(angle);
    float aSin = sin(angle);
    float aCos = cos(angle);
    float newX = aCos * vec.x - aSin * vec.y;
    float newY = aSin * vec.x + aCos * vec.y;
    return Vector(newX, newY);
}

/*
    Recursive step to generate the branches
*/
void generateTreeRec(const Branch & parent, size_t currentDepth) {
    if (currentDepth == m_MaxDepth) return;
    branches.push_back(parent);
    Vector endPos = getEndOfBranch(parent);
    float newLength = parent.length * m_LengthFactor;
    static float halfAngle = m_BranchingAngle / 2.0f;
    Vector leftDirection = rotateVector(parent.direction, halfAngle);
    Vector rightDirection = rotateVector(parent.direction, -halfAngle);
    Branch leftBranch = Branch(leftDirection, endPos, newLength);
    Branch rightBranch = Branch(rightDirection, endPos, newLength);
    generateTreeRec(leftBranch, currentDepth+1);
    generateTreeRec(rightBranch, currentDepth+1);
}

/*
    Creates the tree and starts the recursive call
*/
void generateTree(float branchingAngle, float lengthFactor, size_t maxDepth) {
    m_BranchingAngle = branchingAngle;
    m_LengthFactor = lengthFactor;
    m_MaxDepth = maxDepth;

    Branch trunk = Branch(0.0f, 1.0f, 0.0f, -1.0f, 0.8f);

    generateTreeRec(trunk, 0);
}

/*
    Branches are already created but they cannot be drawn directly.
    We can simple create triangles to draw the brances like:
    --------
    |     /|
    |    / |
    |   /  |
    |  /   |
    | /    |
    |/     |
    --------
    Basically, we have the direction of the branch and we take the vector
    which is perpendicular to the direction. Then we create a vertex for the rectangle with a distance
    DELTA from the initial vertex. That's all.
    In this way, we have a rectangle and we can very easily triangulate.
*/
void transformBranchesToTriangles() {
    for (Branch branch : branches) {
        Vector start = branch.position;
        Vector end = getEndOfBranch(branch);
        Vector perpendicular = rotateVector(branch.direction, -90.0f);
        static float DELTA = 0.005f;
        Vector rStart = start + perpendicular * DELTA;
        Vector rEnd = end + perpendicular * DELTA;
        triangles.push_back(start);
        triangles.push_back(rStart);
        triangles.push_back(rEnd);
        triangles.push_back(end);
        triangles.push_back(start);
        triangles.push_back(rEnd);
    }
}

GLuint VAO;
GLuint VBA;

/*
    Everything else is standard. Just init the VAO and the VBA and load the shaders.
    The vertex shader is just a pass shader and the fragment shader just sets some color.
    Nothing special.
*/

void init() {
    generateTree(120.0f, 1.0f / 1.8f, 8);
    transformBranchesToTriangles();

    glGenVertexArrays(1, &VAO);
    glBindVertexArray(VAO);

    glGenBuffers(1, &VBA);
    glBindBuffer(GL_ARRAY_BUFFER, VBA);

    glBufferData(GL_ARRAY_BUFFER, triangles.size() * sizeof(Vector), &triangles[0], GL_STATIC_DRAW);


    ShaderProgram program = ShaderProgram(Shader("shader.vert", GL_VERTEX_SHADER),
     Shader("shader.frag", GL_FRAGMENT_SHADER) );

     glUseProgram(program.getProgram());

    glVertexAttribPointer(0, 2, GL_FLOAT, GL_FALSE, 0, 0);

    glEnableVertexAttribArray(0);

}

void display() {

    glClear(GL_COLOR_BUFFER_BIT);

    glBindVertexArray(VAO);
    glDrawArrays(GL_TRIANGLES,0, triangles.size());

    glFlush();

}


int main(int argc, char ** argv)
{
    glutInit(&argc, argv);
    glutInitDisplayMode(GLUT_RGBA);
    glutInitWindowSize(512, 512);
    glutInitContextVersion(4,3); // freeglut required
    glutInitContextProfile(GLUT_CORE_PROFILE);
    glutCreateWindow("");
    glewExperimental=GL_TRUE;
    if (glewInit()) {
        cerr << "Problem initializing glew" << endl;
        exit(EXIT_FAILURE);
    }

    init();

    glutDisplayFunc(display);

    glutMainLoop();

    return 0;
}

Note that instead of making the rectangles using 2 triangles, we could have drawn the GL_LINES primitive and also set the width of the line by changing the state with glLineWidth(float)